| 2026 | IPCO | Stochastic Load Balancing with Machine Reservations. | David Alemn Espinosa, Naveen Garg, Sharat Ibrahimpur, Neil Olver, Chaitanya Swamy |
| 2025 | ISNCC | Master-Slave Control Configuration for Adjustable Speed Drives. | Naveen Garg |
| 2025 | WAOA | The Online Piercing Set Problem with Recourse. | Riju Bindua, Minati De, Naveen Garg, Kanav Singla |
| 2024 | FOCS | Fully Dynamic k-Clustering with Fast Update Time and Small Recourse. | Sayan Bhattacharya, Martn Costa, Naveen Garg, Silvio Lattanzi, Nikos Parotsidis |
| 2024 | IPCO | Capacitated Facility Location with Outliers and Uniform Facility Costs. | Rajni Dabas, Naveen Garg, Neelima Gupta |
| 2022 | WAOA | Locating Service and Charging Stations. | Rajni Dabas, Naveen Garg, Neelima Gupta, Dilpreet Kaur |
| 2021 | SODA | Hardness of Approximation for Orienteering with Multiple Time Windows. | Naveen Garg, Sanjeev Khanna, Amit Kumar |
| 2020 | ESA | Dual Half-Integrality for Uncrossable Cut Cover and Its Application to Maximum Half-Integral Flow. | Naveen Garg, Nikhil Kumar |
| 2020 | IPCO | Integer Plane Multiflow Maximisation: Flow-Cut Gap and One-Quarter-Approximation. | Naveen Garg, Nikhil Kumar, Andrs Seb |
| 2020 | SODA | Parallel Machine Scheduling to Minimize Energy Consumption. | Antonios Antoniadis, Naveen Garg, Gunjan Kumar, Nikhil Kumar |
| 2019 | ICALP | Non-Clairvoyant Precedence Constrained Scheduling. | Naveen Garg, Anupam Gupta, Amit Kumar, Sahil Singla |
| 2018 | FOCS | Constant Factor Approximation Algorithm for Weighted Flow Time on a Single Machine in Pseudo-Polynomial Time. | Jatin Batra, Naveen Garg, Amit Kumar |
| 2015 | SODA | New Approximation Schemes for Unsplittable Flow on a Path. | Jatin Batra, Naveen Garg, Amit Kumar, Tobias Mmke, Andreas Wiese |
| 2015 | SODA | Rejecting jobs to Minimize Load and Maximum Flow-time. | Anamitra Roy Choudhury, Syamantak Das, Naveen Garg, Amit Kumar |
| 2013 | ICALP | Minimizing Maximum (Weighted) Flow-Time on Related and Unrelated Machines. | S. Anand, Karl Bringmann, Tobias Friedrich, Naveen Garg, Amit Kumar |
| 2012 | ESA | A 5-Approximation for Capacitated Facility Location. | Manisha Bansal, Naveen Garg, Neelima Gupta |
| 2012 | SODA | Resource augmentation for weighted flow-time explained by dual fitting. | S. Anand, Naveen Garg, Amit Kumar |
| 2011 | ICALP | Meeting Deadlines: How Much Speed Suffices? | S. Anand, Naveen Garg, Nicole Megow |
| 2010 | IPCO | A 3-Approximation for Facility Location with Uniform Capacities. | Ankit Aggarwal, Anand Louis, Manisha Bansal, Naveen Garg, Neelima Gupta, Shubham Gupta, Surabhi Jain |
| 2009 | STOC | A competitive algorithm for minimizing weighted flow time on unrelatedmachines with speed augmentation. | Jivitej S. Chadha, Naveen Garg, Amit Kumar, V. N. Muralidhara |
| 2008 | ISAAC | Minimizing Total Flow-Time: The Unrelated Case. | Naveen Garg, Amit Kumar, V. N. Muralidhara |
| 2008 | SODA | Stochastic analyses for online combinatorial optimization problems. | Naveen Garg, Anupam Gupta, Stefano Leonardi, Piotr Sankowski |
| 2007 | FOCS | Minimizing Average Flow-time: Upper and Lower Bounds. | Naveen Garg, Amit Kumar |
| 2006 | ICALP | Better Algorithms for Minimizing Average Flow-Time on Related Machines. | Naveen Garg, Amit Kumar |
| 2006 | STOC | Minimizing average flow time on related machines. | Naveen Garg, Amit Kumar |
| 2005 | ESA | Heuristic Improvements for Computing Maximum Multicommodity Flow and Minimum Multicut. | Garima Batra, Naveen Garg, Garima Gupta |
| 2005 | SODA | Improved approximation for universal facility location. | Naveen Garg, Rohit Khandekar, Vinayaka Pandit |
| 2005 | STOC | Saving an epsilon: a 2-approximation for the k-MST problem in graphs. | Naveen Garg |
| 2004 | ESA | Fractional Covering with Upper Bounds on the Variables: Solving LPs with Negative Entries. | Naveen Garg, Rohit Khandekar |
| 2003 | ESA | Bandwidth Maximization in Multicasting. | Naveen Garg, Rohit Khandekar, Keshav Kunal, Vinayaka Pandit |
| 2003 | SODA | A combinatorial algorithm for computing a maximum independent set in a t-perfect graph. | Friedrich Eisenbrand, Stefan Funke, Naveen Garg, Jochen Knemann |
| 2002 | FOCS | Fast Approximation Algorithms for Fractional Steiner Forest and Related Problems. | Naveen Garg, Rohit Khandekar |
| 2002 | FOCS | On-Line End-to-End Congestion Control. | Naveen Garg, Neal E. Young |
| 2001 | IPCO | 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 |
| 2001 | STOC | Local search heuristic for k-median and facility location problems. | Vijay Arya, Naveen Garg, Rohit Khandekar, Adam Meyerson, Kamesh Munagala, Vinayaka Pandit |
| 1998 | FOCS | On the Single-Source Unsplittable Flow Problem. | Yefim Dinitz, Naveen Garg, Michel X. Goemans |
| 1998 | FOCS | Faster and Simpler Algorithms for Multicommodity Flow and Other Fractional Packing Problems. | Naveen Garg, Jochen Knemann |
| 1998 | SODA | A Polylogarithmic Approximation Algorithm for the Group Steiner Tree Problem. | Naveen Garg, Goran Konjevod, R. Ravi |
| 1998 | STOC | Minimizing Stall Time in Single and Parallel Disk Systems. | Susanne Albers, Naveen Garg, Stefano Leonardi |
| 1996 | FOCS | A 3-Approximation for the Minimum Tree Spanning k Vertices. | Naveen Garg |
| 1994 | FOCS | Finding separator cuts in planar graphs within twice the optimal | Naveen Garg, Huzur Saran, Vijay V. Vazirani |
| 1994 | ICALP | Multiway Cuts in Directed and Node Weighted Graphs. | Naveen Garg, Vijay V. Vazirani, Mihalis Yannakakis |
| 1994 | SODA | A Scaling Technique for Better Network Design. | Manica Aggarwal, Naveen Garg |
| 1994 | STOC | An O(log k) approximation algorithm for the k minimum spanning tree problem in the plane. | Naveen Garg, Dorit S. Hochbaum |
| 1993 | ICALP | 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 |
| 1993 | IPCO | A polyhedron with all s-t cuts as vertices, and adjacency of cuts. | Naveen Garg, Vijay V. Vazirani |
| 1993 | SODA | Improved Approximation Algorithms for Biconnected Subgraphs via Better Lower Bounding Techniques. | Naveen Garg, Santosh S. Vempala, Aman Singla |
| 1993 | STOC | Approximate max-flow min-(multi)cut theorems and their applications. | Naveen Garg, Vijay V. Vazirani, Mihalis Yannakakis |