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

Naveen Garg Vis

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

*2009
50EENaveen Garg: Minimizing Average Flow-Time. Efficient Algorithms 2009: 187-198
49EEJivitej S. Chadha, Naveen Garg, Amit Kumar, V. N. Muralidhara: A competitive algorithm for minimizing weighted flow time on unrelatedmachines with speed augmentation. STOC 2009: 679-684
2008
48EENaveen Garg, Amit Kumar, V. N. Muralidhara: Minimizing Total Flow-Time: The Unrelated Case. ISAAC 2008: 424-435
47EENaveen Garg, Anupam Gupta, Stefano Leonardi, Piotr Sankowski: Stochastic analyses for online combinatorial optimization problems. SODA 2008: 942-951
2007
46EENaveen Garg, Amit Kumar: Minimizing Average Flow-time : Upper and Lower Bounds. FOCS 2007: 603-613
45EENaveen Garg, Amit Kumar, Vinayaka Pandit: Order Scheduling Models: Hardness and Algorithms. FSTTCS 2007: 96-107
44EENaveen 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
43 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
42EENaveen Garg, Amit Kumar: Better Algorithms for Minimizing Average Flow-Time on Related Machines. ICALP (1) 2006: 181-190
41EENaveen Garg, Amit Kumar: Minimizing average flow time on related machines. STOC 2006: 730-738
2005
40EEGarima Batra, Naveen Garg, Garima Gupta: Heuristic Improvements for Computing Maximum Multicommodity Flow and Minimum Multicut. ESA 2005: 35-46
39EENaveen Garg, Rohit Khandekar, Vinayaka Pandit: Improved approximation for universal facility location. SODA 2005: 959-960
38EENaveen Garg: Saving an epsilon: a 2-approximation for the k-MST problem in graphs. STOC 2005: 396-402
37EENikhil 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
36EENaveen Garg, Rohit Khandekar: Fractional Covering with Upper Bounds on the Variables: Solving LPs with Negative Entries. ESA 2004: 371-382
35EENaveen Garg, Vijay V. Vazirani, Mihalis Yannakakis: Multiway cuts in node weighted graphs. J. Algorithms 50(1): 49-61 (2004)
34EEGuy Even, Naveen Garg, Jochen Könemann, R. Ravi, Amitabh Sinha: Min-max tree covers of graphs. Oper. Res. Lett. 32(4): 309-315 (2004)
33EEVijay 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
32EENaveen Garg, Rohit Khandekar, Keshav Kunal, Vinayaka Pandit: Bandwidth Maximization in Multicasting. ESA 2003: 242-253
31EEGuy Even, Naveen Garg, Jochen Könemann, R. Ravi, Amitabh Sinha: Covering Graphs Using Trees and Stars. RANDOM-APPROX 2003: 24-35
30EEFriedrich 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
29EENaveen Garg, Neal E. Young: On-Line End-to-End Congestion Control. FOCS 2002: 303-312
28EENaveen Garg, Rohit Khandekar: Fast Approximation Algorithms for Fractional Steiner Forest and Related Problems. FOCS 2002: 500-
27EENaveen Garg, Neal E. Young: On-Line End-to-End Congestion Control CoRR cs.DS/0205032: (2002)
26 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
25EENaveen 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
24EEVijay 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
23EESusanne Albers, Naveen Garg, Stefano Leonardi: Minimizing stall time in single and parallel disk systems. J. ACM 47(6): 969-986 (2000)
22 Naveen Garg, Goran Konjevod, R. Ravi: A Polylogarithmic Approximation Algorithm for the Group Steiner Tree Problem. J. Algorithms 37(1): 66-84 (2000)
1999
21EENaveen Garg, Sachin Jain, Chaitanya Swamy: A Randomized Algorithm for Flow Shop Scheduling. FSTTCS 1999: 213-218
20EEYefim Dinitz, Naveen Garg, Michel X. Goemans: On the Single-Source Unsplittable Flow Problem. Combinatorica 19(1): 17-41 (1999)
19 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
18EEYefim Dinitz, Naveen Garg, Michel X. Goemans: On the Single-Source Unsplittable Flow Problem. FOCS 1998: 290-299
17EENaveen Garg, Jochen Könemann: Faster and Simpler Algorithms for Multicommodity Flow and Other Fractional Packing Problems. FOCS 1998: 300-309
16 Naveen Garg, Goran Konjevod, R. Ravi: A Polylogarithmic Approximation Algorithm for the Group Steiner Tree Problem. SODA 1998: 253-259
15EESusanne Albers, Naveen Garg, Stefano Leonardi: Minimizing Stall Time in Single and Parallel Disk Systems. STOC 1998: 454-462
14EEShiva Chaudhuri, Naveen Garg, R. Ravi: The p-Neighbor k-Center Problem. Inf. Process. Lett. 65(3): 131-134 (1998)
1997
13 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)
12 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
11 Naveen Garg: A 3-Approximation for the Minimum Tree Spanning k Vertices. FOCS 1996: 302-309
10 Naveen Garg, Marina Papatriantafilou, Philippas Tsigas: Distributed List Coloring: How To Dynamically Allocate Frequencies To Mobile Base Stations. SPDP 1996: 18-25
9 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
8 Naveen Garg, Huzur Saran, Vijay V. Vazirani: Finding separator cuts in planar graphs within twice the optimal FOCS 1994: 14-23
7EENaveen Garg, Vijay V. Vazirani, Mihalis Yannakakis: Multiway Cuts in Directed and Node Weighted Graphs. ICALP 1994: 487-498
6 Manica Aggarwal, Naveen Garg: A Scaling Technique for Better Network Design. SODA 1994: 233-240
5EENaveen Garg, Dorit S. Hochbaum: An O(log k) approximation algorithm for the k minimum spanning tree problem in the plane. STOC 1994: 432-438
1993
4EENaveen 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 [6]
2Susanne Albers [15] [23]
3S. Arun-Kumar [43]
4Vijay Arya [24] [33]
5Garima Batra [40]
6Jivitej S. Chadha [49]
7Shiva Chaudhuri [14]
8Nikhil R. Devanur [37]
9Yefim Dinitz [18] [20]
10Friedrich Eisenbrand [30]
11Guy Even [31] [34]
12Stefan Funke [30]
13Michel X. Goemans [18] [20]
14Anupam Gupta [47]
15Garima Gupta [40]
16Dorit S. Hochbaum [5] [13]
17Sachin Jain [21]
18Rohit Khandekar [24] [25] [28] [32] [33] [36] [37] [39]
19Jochen Könemann [17] [30] [31] [34] [44]
20Goran Konjevod [16] [22] [25]
21Amit Kumar [41] [42] [45] [46] [48] [49]
22Keshav Kunal [32]
23Stefano Leonardi [15] [23] [47]
24Adam Meyerson [24] [33]
25Kamesh Munagala [24] [33]
26V. N. Muralidhara [48] [49]
27Vinayaka Pandit [24] [32] [33] [37] [39] [45]
28Marina Papatriantafilou [10] [26]
29R. Ravi [14] [16] [22] [25] [31] [34]
30Amin Saberi [37]
31F. Sibel Salman [25]
32Piotr Sankowski [47]
33Huzur Saran [8] [19]
34Aman Singla [2]
35Amitabh Sinha [31] [34]
36Amitabh Sinha II [25]
37Chaitanya Swamy [21]
38Philippas Tsigas [10] [26]
39Vijay V. Vazirani [1] [3] [4] [7] [8] [9] [12] [19] [35] [37]
40Santosh Vempala [2]
41Mihalis Yannakakis [1] [4] [7] [9] [12] [35]
42Neal E. Young [27] [29]

Colors in the list of coauthors

Copyright © Tue Nov 3 08:52:44 2009 by Michael Ley (ley@uni-trier.de)