2008 |
47 | EE | Naveen Garg,
Amit Kumar,
V. N. Muralidhara:
Minimizing Total Flow-Time: The Unrelated Case.
ISAAC 2008: 424-435 |
46 | EE | Naveen Garg,
Anupam Gupta,
Stefano Leonardi,
Piotr Sankowski:
Stochastic analyses for online combinatorial optimization problems.
SODA 2008: 942-951 |
2007 |
45 | EE | Naveen Garg,
Amit Kumar:
Minimizing Average Flow-time : Upper and Lower Bounds.
FOCS 2007: 603-613 |
44 | EE | Naveen Garg,
Amit Kumar,
Vinayaka Pandit:
Order Scheduling Models: Hardness and Algorithms.
FSTTCS 2007: 96-107 |
43 | EE | Naveen Garg,
Jochen Könemann:
Faster and Simpler Algorithms for Multicommodity Flow and Other Fractional Packing Problems.
SIAM J. Comput. 37(2): 630-652 (2007) |
2006 |
42 | | S. Arun-Kumar,
Naveen Garg:
FSTTCS 2006: Foundations of Software Technology and Theoretical Computer Science, 26th International Conference, Kolkata, India, December 13-15, 2006, Proceedings
Springer 2006 |
41 | EE | Naveen Garg,
Amit Kumar:
Better Algorithms for Minimizing Average Flow-Time on Related Machines.
ICALP (1) 2006: 181-190 |
40 | EE | Naveen Garg,
Amit Kumar:
Minimizing average flow time on related machines.
STOC 2006: 730-738 |
2005 |
39 | EE | Garima Batra,
Naveen Garg,
Garima Gupta:
Heuristic Improvements for Computing Maximum Multicommodity Flow and Minimum Multicut.
ESA 2005: 35-46 |
38 | EE | Naveen Garg,
Rohit Khandekar,
Vinayaka Pandit:
Improved approximation for universal facility location.
SODA 2005: 959-960 |
37 | EE | Naveen Garg:
Saving an epsilon: a 2-approximation for the k-MST problem in graphs.
STOC 2005: 396-402 |
36 | EE | Nikhil R. Devanur,
Naveen Garg,
Rohit Khandekar,
Vinayaka Pandit,
Amin Saberi,
Vijay V. Vazirani:
Price of Anarchy, Locality Gap, and a Network Service Provider Game.
WINE 2005: 1046-1055 |
2004 |
35 | EE | Naveen Garg,
Rohit Khandekar:
Fractional Covering with Upper Bounds on the Variables: Solving LPs with Negative Entries.
ESA 2004: 371-382 |
34 | EE | Naveen Garg,
Vijay V. Vazirani,
Mihalis Yannakakis:
Multiway cuts in node weighted graphs.
J. Algorithms 50(1): 49-61 (2004) |
33 | EE | Guy Even,
Naveen Garg,
Jochen Könemann,
R. Ravi,
Amitabh Sinha:
Min-max tree covers of graphs.
Oper. Res. Lett. 32(4): 309-315 (2004) |
32 | EE | Vijay Arya,
Naveen Garg,
Rohit Khandekar,
Adam Meyerson,
Kamesh Munagala,
Vinayaka Pandit:
Local Search Heuristics for k-Median and Facility Location Problems.
SIAM J. Comput. 33(3): 544-562 (2004) |
2003 |
31 | EE | Naveen Garg,
Rohit Khandekar,
Keshav Kunal,
Vinayaka Pandit:
Bandwidth Maximization in Multicasting.
ESA 2003: 242-253 |
30 | EE | Guy Even,
Naveen Garg,
Jochen Könemann,
R. Ravi,
Amitabh Sinha:
Covering Graphs Using Trees and Stars.
RANDOM-APPROX 2003: 24-35 |
29 | EE | Friedrich Eisenbrand,
Stefan Funke,
Naveen Garg,
Jochen Könemann:
A combinatorial algorithm for computing a maximum independent set in a t-perfect graph.
SODA 2003: 517-522 |
2002 |
28 | EE | Naveen Garg,
Neal E. Young:
On-Line End-to-End Congestion Control.
FOCS 2002: 303-312 |
27 | EE | Naveen Garg,
Rohit Khandekar:
Fast Approximation Algorithms for Fractional Steiner Forest and Related Problems.
FOCS 2002: 500- |
26 | EE | Naveen Garg,
Neal E. Young:
On-Line End-to-End Congestion Control
CoRR cs.DS/0205032: (2002) |
25 | | Naveen Garg,
Marina Papatriantafilou,
Philippas Tsigas:
Distributed Long-Lived List Colouring: How to Dynamically Allocate Frequencies in Cellular Networks.
Wireless Networks 8(1): 49-60 (2002) |
2001 |
24 | EE | Naveen Garg,
Rohit Khandekar,
Goran Konjevod,
R. Ravi,
F. Sibel Salman,
Amitabh Sinha II:
On the Integrality Gap of a Natural Formulation of the Single-Sink Buy-at-Bulk Network Design Problem.
IPCO 2001: 170-184 |
23 | EE | Vijay Arya,
Naveen Garg,
Rohit Khandekar,
Adam Meyerson,
Kamesh Munagala,
Vinayaka Pandit:
Local search heuristic for k-median and facility location problems.
STOC 2001: 21-29 |
2000 |
22 | EE | Susanne Albers,
Naveen Garg,
Stefano Leonardi:
Minimizing stall time in single and parallel disk systems.
J. ACM 47(6): 969-986 (2000) |
21 | | Naveen Garg,
Goran Konjevod,
R. Ravi:
A Polylogarithmic Approximation Algorithm for the Group Steiner Tree Problem.
J. Algorithms 37(1): 66-84 (2000) |
1999 |
20 | EE | Naveen Garg,
Sachin Jain,
Chaitanya Swamy:
A Randomized Algorithm for Flow Shop Scheduling.
FSTTCS 1999: 213-218 |
19 | EE | Yefim Dinitz,
Naveen Garg,
Michel X. Goemans:
On the Single-Source Unsplittable Flow Problem.
Combinatorica 19(1): 17-41 (1999) |
18 | | Naveen Garg,
Huzur Saran,
Vijay V. Vazirani:
Finding Separator Cuts in Planar Graphs within Twice the Optimal.
SIAM J. Comput. 29(1): 159-179 (1999) |
1998 |
17 | EE | Yefim Dinitz,
Naveen Garg,
Michel X. Goemans:
On the Single-Source Unsplittable Flow Problem.
FOCS 1998: 290-299 |
16 | EE | Naveen Garg,
Jochen Könemann:
Faster and Simpler Algorithms for Multicommodity Flow and Other Fractional Packing Problems.
FOCS 1998: 300-309 |
15 | | Naveen Garg,
Goran Konjevod,
R. Ravi:
A Polylogarithmic Approximation Algorithm for the Group Steiner Tree Problem.
SODA 1998: 253-259 |
14 | EE | Susanne Albers,
Naveen Garg,
Stefano Leonardi:
Minimizing Stall Time in Single and Parallel Disk Systems.
STOC 1998: 454-462 |
13 | EE | Shiva Chaudhuri,
Naveen Garg,
R. Ravi:
The p-Neighbor k-Center Problem.
Inf. Process. Lett. 65(3): 131-134 (1998) |
1997 |
12 | | Naveen Garg,
Dorit S. Hochbaum:
An O (log k)-Approximation Algorithm for the k Minimum Spanning Tree Problem in the Plane.
Algorithmica 18(1): 111-121 (1997) |
11 | | Naveen Garg,
Vijay V. Vazirani,
Mihalis Yannakakis:
Primal-Dual Approximation Algorithms for Integral Flow and Multicut in Trees.
Algorithmica 18(1): 3-20 (1997) |
1996 |
10 | | Naveen Garg:
A 3-Approximation for the Minimum Tree Spanning k Vertices.
FOCS 1996: 302-309 |
9 | | Naveen Garg,
Marina Papatriantafilou,
Philippas Tsigas:
Distributed List Coloring: How To Dynamically Allocate Frequencies To Mobile Base Stations.
SPDP 1996: 18-25 |
8 | | Naveen Garg,
Vijay V. Vazirani,
Mihalis Yannakakis:
Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications.
SIAM J. Comput. 25(2): 235-251 (1996) |
1994 |
7 | | Naveen Garg,
Huzur Saran,
Vijay V. Vazirani:
Finding separator cuts in planar graphs within twice the optimal
FOCS 1994: 14-23 |
6 | | Naveen Garg,
Vijay V. Vazirani,
Mihalis Yannakakis:
Multiway Cuts in Directed and Node Weighted Graphs.
ICALP 1994: 487-498 |
5 | | Manica Aggarwal,
Naveen Garg:
A Scaling Technique for Better Network Design.
SODA 1994: 233-240 |
1993 |
4 | | Naveen Garg,
Vijay V. Vazirani,
Mihalis Yannakakis:
Primal-Dual Approximation Algorithms for Integral Flow and Multicut in Trees, with Applications to Matching and Set Cover.
ICALP 1993: 64-75 |
3 | | Naveen Garg,
Vijay V. Vazirani:
A polyhedron with all s-t cuts as vertices, and adjacency of cuts.
IPCO 1993: 281-289 |
2 | | Naveen Garg,
Santosh Vempala,
Aman Singla:
Improved Approximation Algorithms for Biconnected Subgraphs via Better Lower Bounding Techniques.
SODA 1993: 103-111 |
1 | EE | Naveen Garg,
Vijay V. Vazirani,
Mihalis Yannakakis:
Approximate max-flow min-(multi)cut theorems and their applications.
STOC 1993: 698-707 |