Naveen Garg

	2012
55		S. Anand, Naveen Garg, Amit Kumar: Resource augmentation for weighted flow-time explained by dual fitting. SODA 2012: 1228-1241
	2011
54		S. Anand, Naveen Garg, Nicole Megow: Meeting Deadlines: How Much Speed Suffices? ICALP (1) 2011: 232-243
53		Nishita Aggarwal, Naveen Garg, Swati Gupta: A 4/3-approximation for TSP on cubic 3-edge-connected graphs CoRR abs/1101.5586: (2011)
	2010
52		Ankit Aggarwal, L. Anand, Manisha Bansal, Naveen Garg, Neelima Gupta, Shubham Gupta, Surabhi Jain: A 3-Approximation for Facility Location with Uniform Capacities. IPCO 2010: 149-162
51		Naveen Garg, Telikepalli Kavitha, Amit Kumar, Kurt Mehlhorn, Julián Mestre: Assigning Papers to Referees. Algorithmica 58(1): 119-136 (2010)
	2009
50		Naveen Garg: Minimizing Average Flow-Time. Efficient Algorithms 2009: 187-198
49		Jivitej 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
48		Naveen Garg, Amit Kumar, V. N. Muralidhara: Minimizing Total Flow-Time: The Unrelated Case. ISAAC 2008: 424-435
47		Naveen Garg, Anupam Gupta, Stefano Leonardi, Piotr Sankowski: Stochastic analyses for online combinatorial optimization problems. SODA 2008: 942-951
	2007
46		Naveen Garg, Amit Kumar: Minimizing Average Flow-time : Upper and Lower Bounds. FOCS 2007: 603-613
45		Naveen Garg, Amit Kumar, Vinayaka Pandit: Order Scheduling Models: Hardness and Algorithms. FSTTCS 2007: 96-107
44		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
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
42		Naveen Garg, Amit Kumar: Better Algorithms for Minimizing Average Flow-Time on Related Machines. ICALP (1) 2006: 181-190
41		Naveen Garg, Amit Kumar: Minimizing average flow time on related machines. STOC 2006: 730-738
	2005
40		Garima Batra, Naveen Garg, Garima Gupta: Heuristic Improvements for Computing Maximum Multicommodity Flow and Minimum Multicut. ESA 2005: 35-46
39		Naveen Garg, Rohit Khandekar, Vinayaka Pandit: Improved approximation for universal facility location. SODA 2005: 959-960
38		Naveen Garg: Saving an epsilon: a 2-approximation for the k-MST problem in graphs. STOC 2005: 396-402
37		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
36		Naveen Garg, Rohit Khandekar: Fractional Covering with Upper Bounds on the Variables: Solving LPs with Negative Entries. ESA 2004: 371-382
35		Naveen Garg, Vijay V. Vazirani, Mihalis Yannakakis: Multiway cuts in node weighted graphs. J. Algorithms 50(1): 49-61 (2004)
34		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)
33		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
32		Naveen Garg, Rohit Khandekar, Keshav Kunal, Vinayaka Pandit: Bandwidth Maximization in Multicasting. ESA 2003: 242-253
31		Guy Even, Naveen Garg, Jochen Könemann, R. Ravi, Amitabh Sinha: Covering Graphs Using Trees and Stars. RANDOM-APPROX 2003: 24-35
30		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
29		Naveen Garg, Neal E. Young: On-Line End-to-End Congestion Control. FOCS 2002: 303-312
28		Naveen Garg, Rohit Khandekar: Fast Approximation Algorithms for Fractional Steiner Forest and Related Problems. FOCS 2002: 500-
27		Naveen 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
25		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
24		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
23		Susanne 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
21		Naveen Garg, Sachin Jain, Chaitanya Swamy: A Randomized Algorithm for Flow Shop Scheduling. FSTTCS 1999: 213-218
20		Yefim 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
18		Yefim Dinitz, Naveen Garg, Michel X. Goemans: On the Single-Source Unsplittable Flow Problem. FOCS 1998: 290-299
17		Naveen 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
15		Susanne Albers, Naveen Garg, Stefano Leonardi: Minimizing Stall Time in Single and Parallel Disk Systems. STOC 1998: 454-462
14		Shiva 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
7		Naveen 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
5		Naveen 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
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		Naveen Garg, Vijay V. Vazirani, Mihalis Yannakakis: Approximate max-flow min-(multi)cut theorems and their applications. STOC 1993: 698-707

Coauthor Index

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

Colors in the list of coauthors

Last update Wed May 30 22:34:44 2012 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page