# Naveen Garg

According to our database

Collaborative distances:

^{1}, Naveen Garg authored at least 58 papers between 1993 and 2018.Collaborative distances:

## Timeline

#### Legend:

Book In proceedings Article PhD thesis Other## Links

#### Homepages:

#### On csauthors.net:

## Bibliography

2018

A 4/3-approximation for TSP on cubic 3-edge-connected graphs.

Oper. Res. Lett., 2018

On Fair Division for Indivisible Items.

Proceedings of the 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2018

A 5-Approximation for Universal Facility Location.

Proceedings of the 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2018

Constant Factor Approximation Algorithm for Weighted Flow Time on a Single Machine in Pseudo-Polynomial Time.

Proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science, 2018

2015

Rejecting jobs to Minimize Load and Maximum Flow-time.

Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015

New Approximation Schemes for Unsplittable Flow on a Path.

Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015

2013

A 3-approximation algorithm for the facility location problem with uniform capacities.

Math. Program., 2013

Minimizing Maximum (Weighted) Flow-Time on Related and Unrelated Machines.

Proceedings of the Automata, Languages, and Programming - 40th International Colloquium, 2013

2012

Resource augmentation for weighted flow-time explained by dual fitting.

Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012

Approximation Algorithms for the Unsplittable Flow Problem on Paths and Trees.

Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2012

A 5-Approximation for Capacitated Facility Location.

Proceedings of the Algorithms - ESA 2012, 2012

2011

Meeting Deadlines: How Much Speed Suffices?

Proceedings of the Automata, Languages and Programming - 38th International Colloquium, 2011

2010

Assigning Papers to Referees.

Algorithmica, 2010

A 3-Approximation for Facility Location with Uniform Capacities.

Proceedings of the Integer Programming and Combinatorial Optimization, 2010

2009

A competitive algorithm for minimizing weighted flow time on unrelatedmachines with speed augmentation.

Proceedings of the 41st Annual ACM Symposium on Theory of Computing, 2009

Minimizing Average Flow-Time.

Proceedings of the Efficient Algorithms, 2009

2008

Stochastic analyses for online combinatorial optimization problems.

Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2008

Minimizing Total Flow-Time: The Unrelated Case.

Proceedings of the Algorithms and Computation, 19th International Symposium, 2008

2007

Order Scheduling Models: Hardness and Algorithms.

Proceedings of the FSTTCS 2007: Foundations of Software Technology and Theoretical Computer Science, 2007

Minimizing Average Flow-time : Upper and Lower Bounds.

Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007), 2007

2006

Minimizing average flow time on related machines.

Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 2006

Better Algorithms for Minimizing Average Flow-Time on Related Machines.

Proceedings of the Automata, Languages and Programming, 33rd International Colloquium, 2006

2005

Price of Anarchy, Locality Gap, and a Network Service Provider Game.

Proceedings of the Internet and Network Economics, First International Workshop, 2005

Saving an epsilon: a 2-approximation for the k-MST problem in graphs.

Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 2005

Improved approximation for universal facility location.

Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005

Heuristic Improvements for Computing Maximum Multicommodity Flow and Minimum Multicut.

Proceedings of the Algorithms, 2005

2004

Local Search Heuristics for k-Median and Facility Location Problems.

SIAM J. Comput., 2004

Min-max tree covers of graphs.

Oper. Res. Lett., 2004

Multiway cuts in node weighted graphs.

J. Algorithms, 2004

Fractional Covering with Upper Bounds on the Variables: Solving LPs with Negative Entries.

Proceedings of the Algorithms, 2004

2003

A combinatorial algorithm for computing a maximum independent set in a t-perfect graph.

Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2003

Covering Graphs Using Trees and Stars.

Proceedings of the Approximation, 2003

Bandwidth Maximization in Multicasting.

Proceedings of the Algorithms, 2003

2002

Distributed Long-Lived List Colouring: How to Dynamically Allocate Frequencies in Cellular Networks.

Wireless Networks, 2002

On-Line End-to-End Congestion Control.

Proceedings of the 43rd Symposium on Foundations of Computer Science (FOCS 2002), 2002

Fast Approximation Algorithms for Fractional Steiner Forest and Related Problems.

Proceedings of the 43rd Symposium on Foundations of Computer Science (FOCS 2002), 2002

2001

Local search heuristic for k-median and facility location problems.

Proceedings of the Proceedings on 33rd Annual ACM Symposium on Theory of Computing, 2001

On the Integrality Gap of a Natural Formulation of the Single-Sink Buy-at-Bulk Network Design Problem.

Proceedings of the Integer Programming and Combinatorial Optimization, 2001

1999

Finding Separator Cuts in Planar Graphs within Twice the Optimal.

SIAM J. Comput., 1999

A Randomized Algorithm for Flow Shop Scheduling.

Proceedings of the Foundations of Software Technology and Theoretical Computer Science, 1999

1998

Inf. Process. Lett., 1998

Minimizing Stall Time in Single and Parallel Disk Systems.

Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, 1998

A Polylogarithmic Approximation Algorithm for the Group Steiner Tree Problem.

Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 1998

Faster and Simpler Algorithms for Multicommodity Flow and Other Fractional Packing Problems.

Proceedings of the 39th Annual Symposium on Foundations of Computer Science, 1998

On the Single-Source Unsplittable Flow Problem.

Proceedings of the 39th Annual Symposium on Foundations of Computer Science, 1998

1997

Primal-Dual Approximation Algorithms for Integral Flow and Multicut in Trees.

Algorithmica, 1997

An O (log k)-Approximation Algorithm for the k Minimum Spanning Tree Problem in the Plane.

Algorithmica, 1997

1996

Distributed List Coloring: How To Dynamically Allocate Frequencies To Mobile Base Stations.

Proceedings of the Eighth IEEE Symposium on Parallel and Distributed Processing, 1996

A 3-Approximation for the Minimum Tree Spanning k Vertices.

Proceedings of the 37th Annual Symposium on Foundations of Computer Science, 1996

1995

A polyhedron with all

*s - t*cuts as vertices, and adjacency of cuts.
Math. Program., 1995

1994

An O(log k) approximation algorithm for the k minimum spanning tree problem in the plane.

Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, 1994

A Scaling Technique for Better Network Design.

Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms. 23-25 January 1994, 1994

Multiway Cuts in Directed and Node Weighted Graphs.

Proceedings of the Automata, Languages and Programming, 21st International Colloquium, 1994

Finding separator cuts in planar graphs within twice the optimal

Proceedings of the 35th Annual Symposium on Foundations of Computer Science, 1994

1993

Approximate max-flow min-(multi)cut theorems and their applications.

Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, 1993

Improved Approximation Algorithms for Biconnected Subgraphs via Better Lower Bounding Techniques.

Proceedings of the Fourth Annual ACM/SIGACT-SIAM Symposium on Discrete Algorithms, 1993

A polyhedron with all s-t cuts as vertices, and adjacency of cuts.

Proceedings of the 3rd Integer Programming and Combinatorial Optimization Conference, Erice, Italy, April 29, 1993

Primal-Dual Approximation Algorithms for Integral Flow and Multicut in Trees, with Applications to Matching and Set Cover.

Proceedings of the Automata, Languages and Programming, 20nd International Colloquium, 1993