dblp.uni-trier.dewww.uni-trier.de

Naveen Garg

List of publications from the DBLP Bibliography Server - FAQ
Coauthor Index - Ask others: ACM DL/Guide - CiteSeer - CSB - Google - MSN - Yahoo
Home Page

2008
47EENaveen Garg, Amit Kumar, V. N. Muralidhara: Minimizing Total Flow-Time: The Unrelated Case. ISAAC 2008: 424-435
46EENaveen Garg, Anupam Gupta, Stefano Leonardi, Piotr Sankowski: Stochastic analyses for online combinatorial optimization problems. SODA 2008: 942-951
2007
45EENaveen Garg, Amit Kumar: Minimizing Average Flow-time : Upper and Lower Bounds. FOCS 2007: 603-613
44EENaveen Garg, Amit Kumar, Vinayaka Pandit: Order Scheduling Models: Hardness and Algorithms. FSTTCS 2007: 96-107
43EENaveen 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
41EENaveen Garg, Amit Kumar: Better Algorithms for Minimizing Average Flow-Time on Related Machines. ICALP (1) 2006: 181-190
40EENaveen Garg, Amit Kumar: Minimizing average flow time on related machines. STOC 2006: 730-738
2005
39EEGarima Batra, Naveen Garg, Garima Gupta: Heuristic Improvements for Computing Maximum Multicommodity Flow and Minimum Multicut. ESA 2005: 35-46
38EENaveen Garg, Rohit Khandekar, Vinayaka Pandit: Improved approximation for universal facility location. SODA 2005: 959-960
37EENaveen Garg: Saving an epsilon: a 2-approximation for the k-MST problem in graphs. STOC 2005: 396-402
36EENikhil 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
35EENaveen Garg, Rohit Khandekar: Fractional Covering with Upper Bounds on the Variables: Solving LPs with Negative Entries. ESA 2004: 371-382
34EENaveen Garg, Vijay V. Vazirani, Mihalis Yannakakis: Multiway cuts in node weighted graphs. J. Algorithms 50(1): 49-61 (2004)
33EEGuy Even, Naveen Garg, Jochen Könemann, R. Ravi, Amitabh Sinha: Min-max tree covers of graphs. Oper. Res. Lett. 32(4): 309-315 (2004)
32EEVijay 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
31EENaveen Garg, Rohit Khandekar, Keshav Kunal, Vinayaka Pandit: Bandwidth Maximization in Multicasting. ESA 2003: 242-253
30EEGuy Even, Naveen Garg, Jochen Könemann, R. Ravi, Amitabh Sinha: Covering Graphs Using Trees and Stars. RANDOM-APPROX 2003: 24-35
29EEFriedrich 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
28EENaveen Garg, Neal E. Young: On-Line End-to-End Congestion Control. FOCS 2002: 303-312
27EENaveen Garg, Rohit Khandekar: Fast Approximation Algorithms for Fractional Steiner Forest and Related Problems. FOCS 2002: 500-
26EENaveen 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
24EENaveen 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
23EEVijay 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
22EESusanne 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
20EENaveen Garg, Sachin Jain, Chaitanya Swamy: A Randomized Algorithm for Flow Shop Scheduling. FSTTCS 1999: 213-218
19EEYefim 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
17EEYefim Dinitz, Naveen Garg, Michel X. Goemans: On the Single-Source Unsplittable Flow Problem. FOCS 1998: 290-299
16EENaveen 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
14EESusanne Albers, Naveen Garg, Stefano Leonardi: Minimizing Stall Time in Single and Parallel Disk Systems. STOC 1998: 454-462
13EEShiva 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
1EENaveen Garg, Vijay V. Vazirani, Mihalis Yannakakis: Approximate max-flow min-(multi)cut theorems and their applications. STOC 1993: 698-707

Coauthor Index

1Manica Aggarwal [5]
2Susanne Albers [14] [22]
3S. Arun-Kumar [42]
4Vijay Arya [23] [32]
5Garima Batra [39]
6Shiva Chaudhuri [13]
7Nikhil R. Devanur [36]
8Yefim Dinitz [17] [19]
9Friedrich Eisenbrand [29]
10Guy Even [30] [33]
11Stefan Funke [29]
12Michel X. Goemans [17] [19]
13Anupam Gupta [46]
14Garima Gupta [39]
15Dorit S. Hochbaum [12]
16Sachin Jain [20]
17Rohit Khandekar [23] [24] [27] [31] [32] [35] [36] [38]
18Jochen Könemann [16] [29] [30] [33] [43]
19Goran Konjevod [15] [21] [24]
20Amit Kumar [40] [41] [44] [45] [47]
21Keshav Kunal [31]
22Stefano Leonardi [14] [22] [46]
23Adam Meyerson [23] [32]
24Kamesh Munagala [23] [32]
25V. N. Muralidhara [47]
26Vinayaka Pandit [23] [31] [32] [36] [38] [44]
27Marina Papatriantafilou [9] [25]
28R. Ravi [13] [15] [21] [24] [30] [33]
29Amin Saberi [36]
30F. Sibel Salman [24]
31Piotr Sankowski [46]
32Huzur Saran [7] [18]
33Aman Singla [2]
34Amitabh Sinha [30] [33]
35Amitabh Sinha II [24]
36Chaitanya Swamy [20]
37Philippas Tsigas [9] [25]
38Vijay V. Vazirani [1] [3] [4] [6] [7] [8] [11] [18] [34] [36]
39Santosh Vempala [2]
40Mihalis Yannakakis [1] [4] [6] [8] [11] [34]
41Neal E. Young [26] [28]

Colors in the list of coauthors

Copyright © Sun May 17 03:24:02 2009 by Michael Ley (ley@uni-trier.de)