Naveen Garg

Publication Activity (10 Years)

Years Active: 1993-2024
Publications (10 Years): 25

Top Topics

Constant Factor Approximation Algorithm

Constant Factor

Top Venues

Publications

Rajni Dabas, Naveen Garg, Neelima Gupta
Capacitated Facility Location with Outliers and Uniform Facility Costs. IPCO (2024)
Rohith Reddy Gangam, Naveen Garg, Parnian Shahkar, Vijay V. Vazirani
The Flow Game: Leximin and Leximax Core Imputations. CoRR (2024)
Jatin Batra, Naveen Garg, Amit Kumar
Constant Factor Approximation Algorithm for Weighted Flow-Time on a Single Machine in PseudoPolynomial Time. SIAM J. Comput. 52 (6) (2023)
Naveen Garg, Nikhil Kumar, András Sebö
Integer plane multiflow maximisation: one-quarter-approximation and gaps. Math. Program. 195 (1) (2022)
Rajni Dabas, Naveen Garg, Neelima Gupta, Dilpreet Kaur
Locating Service and Charging Stations. WAOA (2022)
Bhaskar Ray Chaudhury, Yun Kuen Cheung, Jugal Garg, Naveen Garg, Martin Hoefer, Kurt Mehlhorn
Fair Division of Indivisible Goods for a Class of Concave Valuations. J. Artif. Intell. Res. 74 (2022)
Naveen Garg, Sanjeev Khanna, Amit Kumar
Hardness of Approximation for Orienteering with Multiple Time Windows. SODA (2021)
Naveen Garg, Nikhil Kumar, András Sebö
Integer Plane Multiflow Maximisation: Flow-Cut Gap and One-Quarter-Approximation. IPCO (2020)
Naveen Garg, Nikhil Kumar
Dual Half-Integrality for Uncrossable Cut Cover and Its Application to Maximum Half-Integral Flow. ESA (2020)
Antonios Antoniadis, Naveen Garg, Gunjan Kumar, Nikhil Kumar
Parallel Machine Scheduling to Minimize Energy Consumption. SODA (2020)
Naveen Garg, Nikhil Kumar, András Sebö
Integer Plane Multiflow Maximisation: Flow-Cut Gap and One-Quarter-Approximation. CoRR (2020)
Naveen Garg, Nikhil Kumar
Dual Half-integrality for Uncrossable Cut Cover and its Application to Maximum Half-Integral Flow. CoRR (2020)
Naveen Garg, Anupam Gupta, Amit Kumar, Sahil Singla
Non-clairvoyant Precedence Constrained Scheduling. CoRR (2019)
Antonios Antoniadis, Naveen Garg, Gunjan Kumar, Nikhil Kumar
Parallel Machine Scheduling to Minimize Energy Consumption. CoRR (2019)
Naveen Garg, Anupam Gupta, Amit Kumar, Sahil Singla
Non-Clairvoyant Precedence Constrained Scheduling. ICALP (2019)
Yun Kuen Cheung, Bhaskar Chaudhuri, Jugal Garg, Naveen Garg, Martin Hoefer, Kurt Mehlhorn
On Fair Division of Indivisible Items. CoRR (2018)
Anamitra Roy Choudhury, Syamantak Das, Naveen Garg, Amit Kumar
Rejecting jobs to minimize load and maximum flow-time. J. Comput. Syst. Sci. 91 (2018)
Jatin Batra, Naveen Garg, Amit Kumar
Constant Factor Approximation Algorithm for Weighted Flow Time on a Single Machine in Pseudo-Polynomial Time. FOCS (2018)
Manisha Bansal, Naveen Garg, Neelima Gupta
A 5-Approximation for Universal Facility Location. FSTTCS (2018)
Bhaskar Ray Chaudhury, Yun Kuen Cheung, Jugal Garg, Naveen Garg, Martin Hoefer, Kurt Mehlhorn
On Fair Division for Indivisible Items. FSTTCS (2018)
Nishita Agarwal, Naveen Garg, Swati Gupta
A 4/3-approximation for TSP on cubic 3-edge-connected graphs. Oper. Res. Lett. 46 (4) (2018)
Jatin Batra, Naveen Garg, Amit Kumar
Constant Factor Approximation Algorithm for Weighted Flow Time on a Single Machine in Pseudo-polynomial time. CoRR (2018)
S. Anand, Karl Bringmann, Tobias Friedrich, Naveen Garg, Amit Kumar
Minimizing Maximum (Weighted) Flow-Time on Related and Unrelated Machines. Algorithmica 77 (2) (2017)
Jatin Batra, Naveen Garg, Amit Kumar, Tobias Mömke, Andreas Wiese
New Approximation Schemes for Unsplittable Flow on a Path. SODA (2015)
Anamitra Roy Choudhury, Syamantak Das, Naveen Garg, Amit Kumar
Rejecting jobs to Minimize Load and Maximum Flow-time. SODA (2015)
Anamitra Roy Choudhury, Syamantak Das, Naveen Garg, Amit Kumar
Rejecting Jobs to Minimize Load and Maximum Flow-time. CoRR (2014)
Ankit Aggarwal, Anand Louis, Manisha Bansal, Naveen Garg, Neelima Gupta, Shubham Gupta, Surabhi Jain
A 3-approximation algorithm for the facility location problem with uniform capacities. Math. Program. 141 (1-2) (2013)
S. Anand, Karl Bringmann, Tobias Friedrich, Naveen Garg, Amit Kumar
Minimizing Maximum (Weighted) Flow-Time on Related and Unrelated Machines. ICALP (1) (2013)
Manisha Bansal, Naveen Garg, Neelima Gupta
A 5-Approximation for Capacitated Facility Location. ESA (2012)
S. Anand, Naveen Garg, Amit Kumar
Resource augmentation for weighted flow-time explained by dual fitting. SODA (2012)
Khaled M. Elbassioni, Naveen Garg, Divya Gupta, Amit Kumar, Vishal Narula, Arindam Pal
Approximation Algorithms for the Unsplittable Flow Problem on Paths and Trees. FSTTCS (2012)
Nishita Aggarwal, Naveen Garg, Swati Gupta
A 4/3-approximation for TSP on cubic 3-edge-connected graphs CoRR (2011)
S. Anand, Naveen Garg, Nicole Megow
Meeting Deadlines: How Much Speed Suffices? ICALP (1) (2011)
Naveen Garg, Telikepalli Kavitha, Amit Kumar, Kurt Mehlhorn, Julián Mestre
Assigning Papers to Referees. Algorithmica 58 (1) (2010)
Ankit Aggarwal, Anand Louis, Manisha Bansal, Naveen Garg, Neelima Gupta, Shubham Gupta, Surabhi Jain
A 3-Approximation for Facility Location with Uniform Capacities. IPCO (2010)
Naveen Garg
Minimizing Average Flow-Time. Efficient Algorithms (2009)
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)
Naveen Garg, Anupam Gupta, Stefano Leonardi, Piotr Sankowski
Stochastic analyses for online combinatorial optimization problems. SODA (2008)
Naveen Garg, Amit Kumar, V. N. Muralidhara
Minimizing Total Flow-Time: The Unrelated Case. ISAAC (2008)
Naveen Garg, Jochen Könemann
Faster and Simpler Algorithms for Multicommodity Flow and Other Fractional Packing Problems. SIAM J. Comput. 37 (2) (2007)
Naveen Garg, Amit Kumar, Vinayaka Pandit
Order Scheduling Models: Hardness and Algorithms. FSTTCS (2007)
Naveen Garg, Amit Kumar
Minimizing Average Flow-time : Upper and Lower Bounds. FOCS (2007)
Naveen Garg, Amit Kumar
Minimizing average flow time on related machines. STOC (2006)
Naveen Garg, Amit Kumar
Better Algorithms for Minimizing Average Flow-Time on Related Machines. ICALP (1) (2006)
Garima Batra, Naveen Garg, Garima Gupta
Heuristic Improvements for Computing Maximum Multicommodity Flow and Minimum Multicut. ESA (2005)
Naveen Garg
Saving an epsilon: a 2-approximation for the k-MST problem in graphs. STOC (2005)
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)
Naveen Garg, Rohit Khandekar, Vinayaka Pandit
Improved approximation for universal facility location. SODA (2005)
Guy Even, Naveen Garg, Jochen Könemann, R. Ravi, Amitabh Sinha
Min-max tree covers of graphs. Oper. Res. Lett. 32 (4) (2004)
Naveen Garg, Vijay V. Vazirani, Mihalis Yannakakis
Multiway cuts in node weighted graphs. J. Algorithms 50 (1) (2004)
Naveen Garg, Rohit Khandekar
Fractional Covering with Upper Bounds on the Variables: Solving LPs with Negative Entries. ESA (2004)
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) (2004)
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)
Guy Even, Naveen Garg, Jochen Könemann, R. Ravi, Amitabh Sinha
Covering Graphs Using Trees and Stars. RANDOM-APPROX (2003)
Naveen Garg, Rohit Khandekar, Keshav Kunal, Vinayaka Pandit
Bandwidth Maximization in Multicasting. ESA (2003)
Naveen Garg, Neal E. Young
On-Line End-to-End Congestion Control. FOCS (2002)
Naveen Garg, Marina Papatriantafilou, Philippas Tsigas
Distributed Long-Lived List Colouring: How to Dynamically Allocate Frequencies in Cellular Networks. Wirel. Networks 8 (1) (2002)
Naveen Garg, Neal E. Young
On-Line End-to-End Congestion Control CoRR (2002)
Naveen Garg, Rohit Khandekar
Fast Approximation Algorithms for Fractional Steiner Forest and Related Problems. FOCS (2002)
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)
Vijay Arya, Naveen Garg, Rohit Khandekar, Adam Meyerson, Kamesh Munagala, Vinayaka Pandit
Local search heuristic for k-median and facility location problems. STOC (2001)
Susanne Albers, Naveen Garg, Stefano Leonardi
Minimizing stall time in single and parallel disk systems. J. ACM 47 (6) (2000)
Naveen Garg, Goran Konjevod, R. Ravi
A Polylogarithmic Approximation Algorithm for the Group Steiner Tree Problem. J. Algorithms 37 (1) (2000)
Yefim Dinitz, Naveen Garg, Michel X. Goemans
On the Single-Source Unsplittable Flow Problem. Comb. 19 (1) (1999)
Naveen Garg, Huzur Saran, Vijay V. Vazirani
Finding Separator Cuts in Planar Graphs within Twice the Optimal. SIAM J. Comput. 29 (1) (1999)
Naveen Garg, Sachin Jain, Chaitanya Swamy
A Randomized Algorithm for Flow Shop Scheduling. FSTTCS (1999)
Yefim Dinitz, Naveen Garg, Michel X. Goemans
On the Single-Source Unsplittable Flow Problem. FOCS (1998)
Naveen Garg, Goran Konjevod, R. Ravi
A Polylogarithmic Approximation Algorithm for the Group Steiner Tree Problem. SODA (1998)
Susanne Albers, Naveen Garg, Stefano Leonardi
Minimizing Stall Time in Single and Parallel Disk Systems. STOC (1998)
Shiva Chaudhuri, Naveen Garg, R. Ravi
-Center Problem. Inf. Process. Lett. 65 (3) (1998)
Naveen Garg, Jochen Könemann
Faster and Simpler Algorithms for Multicommodity Flow and Other Fractional Packing Problems. FOCS (1998)
Naveen Garg, Vijay V. Vazirani, Mihalis Yannakakis
Primal-Dual Approximation Algorithms for Integral Flow and Multicut in Trees. Algorithmica 18 (1) (1997)
Naveen Garg, Dorit S. Hochbaum
An O (log k)-Approximation Algorithm for the k Minimum Spanning Tree Problem in the Plane. Algorithmica 18 (1) (1997)
Naveen Garg
A 3-Approximation for the Minimum Tree Spanning k Vertices. FOCS (1996)
Naveen Garg, Marina Papatriantafilou, Philippas Tsigas
Distributed List Coloring: How To Dynamically Allocate Frequencies To Mobile Base Stations. SPDP (1996)
Naveen Garg, Vijay V. Vazirani, Mihalis Yannakakis
Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications. SIAM J. Comput. 25 (2) (1996)
Naveen Garg, Vijay V. Vazirani
cuts as vertices, and adjacency of cuts. Math. Program. 70 (1995)
Manica Aggarwal, Naveen Garg
A Scaling Technique for Better Network Design. SODA (1994)
Naveen Garg, Huzur Saran, Vijay V. Vazirani
Finding separator cuts in planar graphs within twice the optimal FOCS (1994)
Naveen Garg, Vijay V. Vazirani, Mihalis Yannakakis
Multiway Cuts in Directed and Node Weighted Graphs. ICALP (1994)
Naveen Garg, Dorit S. Hochbaum
An O(log k) approximation algorithm for the k minimum spanning tree problem in the plane. STOC (1994)
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)
Naveen Garg, Santosh S. Vempala, Aman Singla
Improved Approximation Algorithms for Biconnected Subgraphs via Better Lower Bounding Techniques. SODA (1993)
Naveen Garg, Vijay V. Vazirani
A polyhedron with all s-t cuts as vertices, and adjacency of cuts. IPCO (1993)
Naveen Garg, Vijay V. Vazirani, Mihalis Yannakakis
Approximate max-flow min-(multi)cut theorems and their applications. STOC (1993)