Naveen Garg

Orcid: 0000-0001-7923-4464

Affiliations:
  • Indian Institute of Technology Delhi, India
  • Max Planck Institute for Informatics, Saarbrücken, Germany (former)


According to our database1, Naveen Garg authored at least 69 papers between 1993 and 2024.

Collaborative distances:

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Dataset
Other 

Links

Online presence:

On csauthors.net:

Bibliography

2024
The Flow Game: Leximin and Leximax Core Imputations.
CoRR, 2024

Capacitated Facility Location with Outliers and Uniform Facility Costs.
Proceedings of the Integer Programming and Combinatorial Optimization, 2024

2023
Constant Factor Approximation Algorithm for Weighted Flow-Time on a Single Machine in PseudoPolynomial Time.
SIAM J. Comput., December, 2023

2022
Integer plane multiflow maximisation: one-quarter-approximation and gaps.
Math. Program., 2022

Fair Division of Indivisible Goods for a Class of Concave Valuations.
J. Artif. Intell. Res., 2022

Locating Service and Charging Stations.
Proceedings of the Approximation and Online Algorithms - 20th International Workshop, 2022

2021
Hardness of Approximation for Orienteering with Multiple Time Windows.
Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

2020
Parallel Machine Scheduling to Minimize Energy Consumption.
Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

Integer Plane Multiflow Maximisation: Flow-Cut Gap and One-Quarter-Approximation.
Proceedings of the Integer Programming and Combinatorial Optimization, 2020

Dual Half-Integrality for Uncrossable Cut Cover and Its Application to Maximum Half-Integral Flow.
Proceedings of the 28th Annual European Symposium on Algorithms, 2020

2019
Non-Clairvoyant Precedence Constrained Scheduling.
Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, 2019

2018
A 4/3-approximation for TSP on cubic 3-edge-connected graphs.
Oper. Res. Lett., 2018

Rejecting jobs to minimize load and maximum flow-time.
J. Comput. Syst. Sci., 2018

On Fair Division of Indivisible Items.
CoRR, 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

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

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

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
A 4/3-approximation for TSP on cubic 3-edge-connected graphs
CoRR, 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
Faster and Simpler Algorithms for Multicommodity Flow and Other Fractional Packing Problems.
SIAM J. Comput., 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.
Wirel. 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

2000
A Polylogarithmic Approximation Algorithm for the Group Steiner Tree Problem.
J. Algorithms, 2000

Minimizing stall time in single and parallel disk systems.
J. ACM, 2000

1999
Finding Separator Cuts in Planar Graphs within Twice the Optimal.
SIAM J. Comput., 1999

On the Single-Source Unsplittable Flow Problem.
Comb., 1999

A Randomized Algorithm for Flow Shop Scheduling.
Proceedings of the Foundations of Software Technology and Theoretical Computer Science, 1999

1998
The <i>p</i>-Neighbor <i>k</i>-Center Problem.
Inf. Process. Lett., 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
Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications.
SIAM J. Comput., 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<i>s - t</i> cuts as vertices, and adjacency of cuts.
Math. Program., 1995

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

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


  Loading...