Naveen Garg

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

Collaborative distances:

• Dijkstra number of three.
• Erdős number of three.

2024

The Flow Game: Leximin and Leximax Core Imputations.

Rohith Reddy Gangam, Naveen Garg, Parnian Shahkar, Vijay V. Vazirani

CoRR, 2024

Capacitated Facility Location with Outliers and Uniform Facility Costs.

Rajni Dabas, Naveen Garg, Neelima Gupta

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.

Jatin Batra, Naveen Garg, Amit Kumar

SIAM J. Comput., December, 2023

2022

Integer plane multiflow maximisation: one-quarter-approximation and gaps.

Naveen Garg, Nikhil Kumar, András Sebö

Math. Program., 2022

Fair Division of Indivisible Goods for a Class of Concave Valuations.

Bhaskar Ray Chaudhury, Yun Kuen Cheung, Jugal Garg, Naveen Garg, Martin Hoefer, Kurt Mehlhorn

J. Artif. Intell. Res., 2022

Locating Service and Charging Stations.

Rajni Dabas, Naveen Garg, Neelima Gupta, Dilpreet Kaur

Proceedings of the Approximation and Online Algorithms - 20th International Workshop, 2022

2021

Hardness of Approximation for Orienteering with Multiple Time Windows.

Naveen Garg, Sanjeev Khanna, Amit Kumar

Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

2020

Parallel Machine Scheduling to Minimize Energy Consumption.

Antonios Antoniadis, Naveen Garg, Gunjan Kumar, Nikhil Kumar

Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

Integer Plane Multiflow Maximisation: Flow-Cut Gap and One-Quarter-Approximation.

Naveen Garg, Nikhil Kumar, András Sebö

Proceedings of the Integer Programming and Combinatorial Optimization, 2020

Dual Half-Integrality for Uncrossable Cut Cover and Its Application to Maximum Half-Integral Flow.

Naveen Garg, Nikhil Kumar

Proceedings of the 28th Annual European Symposium on Algorithms, 2020

2019

Non-Clairvoyant Precedence Constrained Scheduling.

Naveen Garg, Anupam Gupta, Amit Kumar, Sahil Singla

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.

Nishita Agarwal, Naveen Garg, Swati Gupta

Oper. Res. Lett., 2018

Rejecting jobs to minimize load and maximum flow-time.

Anamitra Roy Choudhury, Syamantak Das, Naveen Garg, Amit Kumar

J. Comput. Syst. Sci., 2018

On Fair Division of Indivisible Items.

Yun Kuen Cheung, Bhaskar Chaudhuri, Jugal Garg, Naveen Garg, Martin Hoefer, Kurt Mehlhorn

CoRR, 2018

On Fair Division for Indivisible Items.

Bhaskar Ray Chaudhury, Yun Kuen Cheung, Jugal Garg, Naveen Garg, Martin Hoefer, Kurt Mehlhorn

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

A 5-Approximation for Universal Facility Location.

Manisha Bansal, Naveen Garg, Neelima Gupta

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.

Jatin Batra, Naveen Garg, Amit Kumar

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

2017

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

S. Anand, Karl Bringmann, Tobias Friedrich, Naveen Garg, Amit Kumar

Algorithmica, 2017

2015

New Approximation Schemes for Unsplittable Flow on a Path.

Jatin Batra, Naveen Garg, Amit Kumar, Tobias Mömke, Andreas Wiese

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.

Ankit Aggarwal, Anand Louis, Manisha Bansal, Naveen Garg, Neelima Gupta, Shubham Gupta, Surabhi Jain

Math. Program., 2013

2012

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

S. Anand, Naveen Garg, Amit Kumar

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

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

Khaled M. Elbassioni, Naveen Garg, Divya Gupta, Amit Kumar, Vishal Narula, Arindam Pal

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

A 5-Approximation for Capacitated Facility Location.

Manisha Bansal, Naveen Garg, Neelima Gupta

Proceedings of the Algorithms - ESA 2012, 2012

2011

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

Nishita Aggarwal, Naveen Garg, Swati Gupta

CoRR, 2011

Meeting Deadlines: How Much Speed Suffices?

S. Anand, Naveen Garg, Nicole Megow

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

2010

Assigning Papers to Referees.

Naveen Garg, Telikepalli Kavitha, Amit Kumar, Kurt Mehlhorn, Julián Mestre

Algorithmica, 2010

A 3-Approximation for Facility Location with Uniform Capacities.

Ankit Aggarwal, Anand Louis, Manisha Bansal, Naveen Garg, Neelima Gupta, Shubham Gupta, Surabhi Jain

Proceedings of the Integer Programming and Combinatorial Optimization, 2010

2009

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

Jivitej S. Chadha, Naveen Garg, Amit Kumar, V. N. Muralidhara

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

Minimizing Average Flow-Time.

Naveen Garg

Proceedings of the Efficient Algorithms, 2009

2008

Stochastic analyses for online combinatorial optimization problems.

Naveen Garg, Anupam Gupta, Stefano Leonardi, Piotr Sankowski

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

Minimizing Total Flow-Time: The Unrelated Case.

Naveen Garg, Amit Kumar, V. N. Muralidhara

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

2007

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

Naveen Garg, Jochen Könemann

SIAM J. Comput., 2007

Order Scheduling Models: Hardness and Algorithms.

Naveen Garg, Amit Kumar, Vinayaka Pandit

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

Minimizing Average Flow-time : Upper and Lower Bounds.

Naveen Garg, Amit Kumar

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

2006

Minimizing average flow time on related machines.

Naveen Garg, Amit Kumar

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

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

Naveen Garg, Amit Kumar

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

2005

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

Nikhil R. Devanur, Naveen Garg, Rohit Khandekar, Vinayaka Pandit, Amin Saberi, Vijay V. Vazirani

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

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

Naveen Garg

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

Improved approximation for universal facility location.

Naveen Garg, Rohit Khandekar, Vinayaka Pandit

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

Heuristic Improvements for Computing Maximum Multicommodity Flow and Minimum Multicut.

Garima Batra, Naveen Garg, Garima Gupta

Proceedings of the Algorithms, 2005

2004

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

Vijay Arya, Naveen Garg, Rohit Khandekar, Adam Meyerson, Kamesh Munagala, Vinayaka Pandit

SIAM J. Comput., 2004

Min-max tree covers of graphs.

Guy Even, Naveen Garg, Jochen Könemann, R. Ravi, Amitabh Sinha

Oper. Res. Lett., 2004

Multiway cuts in node weighted graphs.

Naveen Garg, Vijay V. Vazirani, Mihalis Yannakakis

J. Algorithms, 2004

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

Naveen Garg, Rohit Khandekar

Proceedings of the Algorithms, 2004

2003

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

Friedrich Eisenbrand, Stefan Funke, Naveen Garg, Jochen Könemann

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

Covering Graphs Using Trees and Stars.

Guy Even, Naveen Garg, Jochen Könemann, R. Ravi, Amitabh Sinha

Proceedings of the Approximation, 2003

Bandwidth Maximization in Multicasting.

Naveen Garg, Rohit Khandekar, Keshav Kunal, Vinayaka Pandit

Proceedings of the Algorithms, 2003

2002

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

Naveen Garg, Marina Papatriantafilou, Philippas Tsigas

Wirel. Networks, 2002

On-Line End-to-End Congestion Control.

Naveen Garg, Neal E. Young

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

Fast Approximation Algorithms for Fractional Steiner Forest and Related Problems.

Naveen Garg, Rohit Khandekar

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

2001

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

Vijay Arya, Naveen Garg, Rohit Khandekar, Adam Meyerson, Kamesh Munagala, Vinayaka Pandit

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.

Naveen Garg, Rohit Khandekar, Goran Konjevod, R. Ravi, F. Sibel Salman, Amitabh Sinha II

Proceedings of the Integer Programming and Combinatorial Optimization, 2001

2000

A Polylogarithmic Approximation Algorithm for the Group Steiner Tree Problem.

Naveen Garg, Goran Konjevod, R. Ravi

J. Algorithms, 2000

Minimizing stall time in single and parallel disk systems.

Susanne Albers, Naveen Garg, Stefano Leonardi

J. ACM, 2000

1999

Finding Separator Cuts in Planar Graphs within Twice the Optimal.

Naveen Garg, Huzur Saran, Vijay V. Vazirani

SIAM J. Comput., 1999

On the Single-Source Unsplittable Flow Problem.

Yefim Dinitz, Naveen Garg, Michel X. Goemans

Comb., 1999

A Randomized Algorithm for Flow Shop Scheduling.

Naveen Garg, Sachin Jain, Chaitanya Swamy

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

1998

The <i>p</i>-Neighbor <i>k</i>-Center Problem.

Shiva Chaudhuri, Naveen Garg, R. Ravi

Inf. Process. Lett., 1998

1997

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

Naveen Garg, Vijay V. Vazirani, Mihalis Yannakakis

Algorithmica, 1997

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

Naveen Garg, Dorit S. Hochbaum

Algorithmica, 1997

1996

Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications.

Naveen Garg, Vijay V. Vazirani, Mihalis Yannakakis

SIAM J. Comput., 1996

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

Naveen Garg, Marina Papatriantafilou, Philippas Tsigas

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

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

Naveen Garg

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.

Naveen Garg, Vijay V. Vazirani

Math. Program., 1995

1994

A Scaling Technique for Better Network Design.

Manica Aggarwal, Naveen Garg

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

Multiway Cuts in Directed and Node Weighted Graphs.

Naveen Garg, Vijay V. Vazirani, Mihalis Yannakakis

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

1993

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

Naveen Garg, Santosh S. Vempala, Aman Singla

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.

Naveen Garg, Vijay V. Vazirani

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.

Naveen Garg, Vijay V. Vazirani, Mihalis Yannakakis

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