Naveen Garg - RankMe

91 papers A* 30A 5B 8Journal 33Unranked 13

Year	Rank	Type	Title / Venue / Authors
2025	—	`conf`	Approximating Optimal Broadcast of Files in a Hose-Model Network. FSTTCS Thomas Erlebach, Naveen Garg, Sukriti Gupta, Amitabh Trehan
2025	B	`conf`	The Online Piercing Set Problem with Recourse. WAOA Riju Bindua, Minati De, Naveen Garg, Kanav Singla
2024	B	`conf`	Capacitated Facility Location with Outliers and Uniform Facility Costs. IPCO Rajni Dabas, Naveen Garg, Neelima Gupta
2024	J	`jnl`	Fully Dynamic CoRR Sayan Bhattacharya, Martín Costa, Naveen Garg, Silvio Lattanzi, Nikos Parotsidis
2024	A*	`conf`	Fully Dynamic k-Clustering with Fast Update Time and Small Recourse. FOCS Sayan Bhattacharya, Martín Costa, Naveen Garg, Silvio Lattanzi, Nikos Parotsidis
2024	J	`jnl`	The Flow Game: Leximin and Leximax Core Imputations. CoRR Rohith Reddy Gangam, Naveen Garg, Parnian Shahkar, Vijay V. Vazirani
2023	J	`jnl`	Constant Factor Approximation Algorithm for Weighted Flow-Time on a Single Machine in PseudoPolynomial Time. SIAM J. Comput. Jatin Batra, Naveen Garg, Amit Kumar
2022	J	`jnl`	Fair Division of Indivisible Goods for a Class of Concave Valuations. J. Artif. Intell. Res. Bhaskar Ray Chaudhury, Yun Kuen Cheung, Jugal Garg, Naveen Garg, Martin Hoefer, Kurt Mehlhorn
2022	J	`jnl`	Integer plane multiflow maximisation: one-quarter-approximation and gaps. Math. Program. Naveen Garg, Nikhil Kumar, András Sebö
2022	B	`conf`	Locating Service and Charging Stations. WAOA Rajni Dabas, Naveen Garg, Neelima Gupta, Dilpreet Kaur
2021	A*	`conf`	Hardness of Approximation for Orienteering with Multiple Time Windows. SODA Naveen Garg, Sanjeev Khanna, Amit Kumar
2020	A	`conf`	Dual Half-Integrality for Uncrossable Cut Cover and Its Application to Maximum Half-Integral Flow. ESA Naveen Garg, Nikhil Kumar
2020	J	`jnl`	Dual Half-integrality for Uncrossable Cut Cover and its Application to Maximum Half-Integral Flow. CoRR Naveen Garg, Nikhil Kumar
2020	B	`conf`	Integer Plane Multiflow Maximisation: Flow-Cut Gap and One-Quarter-Approximation. IPCO Naveen Garg, Nikhil Kumar, András Sebö
2020	J	`jnl`	Integer Plane Multiflow Maximisation: Flow-Cut Gap and One-Quarter-Approximation. CoRR Naveen Garg, Nikhil Kumar, András Sebö
2020	A*	`conf`	Parallel Machine Scheduling to Minimize Energy Consumption. SODA Antonios Antoniadis, Naveen Garg, Gunjan Kumar, Nikhil Kumar
2019	A*	`conf`	Non-Clairvoyant Precedence Constrained Scheduling. ICALP Naveen Garg, Anupam Gupta, Amit Kumar, Sahil Singla
2019	J	`jnl`	Non-clairvoyant Precedence Constrained Scheduling. CoRR Naveen Garg, Anupam Gupta, Amit Kumar, Sahil Singla
2019	J	`jnl`	Parallel Machine Scheduling to Minimize Energy Consumption. CoRR Antonios Antoniadis, Naveen Garg, Gunjan Kumar, Nikhil Kumar
2018	J	`jnl`	A 4/3-approximation for TSP on cubic 3-edge-connected graphs. Oper. Res. Lett. Nishita Agarwal, Naveen Garg, Swati Gupta
2018	—	`conf`	A 5-Approximation for Universal Facility Location. FSTTCS Manisha Bansal, Naveen Garg, Neelima Gupta
2018	A*	`conf`	Constant Factor Approximation Algorithm for Weighted Flow Time on a Single Machine in Pseudo-Polynomial Time. FOCS Jatin Batra, Naveen Garg, Amit Kumar
2018	J	`jnl`	Constant Factor Approximation Algorithm for Weighted Flow Time on a Single Machine in Pseudo-polynomial time. CoRR Jatin Batra, Naveen Garg, Amit Kumar
2018	—	`conf`	On Fair Division for Indivisible Items. FSTTCS Bhaskar Ray Chaudhury, Yun Kuen Cheung, Jugal Garg, Naveen Garg, Martin Hoefer, Kurt Mehlhorn
2018	J	`jnl`	On Fair Division of Indivisible Items. CoRR Yun Kuen Cheung, Bhaskar Chaudhuri, Jugal Garg, Naveen Garg, Martin Hoefer, Kurt Mehlhorn
2018	J	`jnl`	Rejecting jobs to minimize load and maximum flow-time. J. Comput. Syst. Sci. Anamitra Roy Choudhury, Syamantak Das, Naveen Garg, Amit Kumar
2017	J	`jnl`	Minimizing Maximum (Weighted) Flow-Time on Related and Unrelated Machines. Algorithmica S. Anand, Karl Bringmann, Tobias Friedrich, Naveen Garg, Amit Kumar
2015	—	`ed.`	Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2015, Princeton, NJ, USA, August 24-26, 2015 APPROX-RANDOM Naveen Garg, Klaus Jansen, Anup Rao, José D. P. Rolim
2015	A*	`conf`	New Approximation Schemes for Unsplittable Flow on a Path. SODA Jatin Batra, Naveen Garg, Amit Kumar, Tobias Mömke, Andreas Wiese
2015	A*	`conf`	Rejecting jobs to Minimize Load and Maximum Flow-time. SODA Anamitra Roy Choudhury, Syamantak Das, Naveen Garg, Amit Kumar
2014	J	`jnl`	Rejecting Jobs to Minimize Load and Maximum Flow-time. CoRR Anamitra Roy Choudhury, Syamantak Das, Naveen Garg, Amit Kumar
2013	J	`jnl`	A 3-approximation algorithm for the facility location problem with uniform capacities. Math. Program. Ankit Aggarwal, Anand Louis, Manisha Bansal, Naveen Garg, Neelima Gupta, Shubham Gupta, Surabhi Jain
2013	—	`conf`	Minimizing Maximum (Weighted) Flow-Time on Related and Unrelated Machines. ICALP (1) S. Anand, Karl Bringmann, Tobias Friedrich, Naveen Garg, Amit Kumar
2012	A	`conf`	A 5-Approximation for Capacitated Facility Location. ESA Manisha Bansal, Naveen Garg, Neelima Gupta
2012	—	`conf`	Approximation Algorithms for the Unsplittable Flow Problem on Paths and Trees. FSTTCS Khaled M. Elbassioni, Naveen Garg, Divya Gupta, Amit Kumar, Vishal Narula, Arindam Pal
2012	A*	`conf`	Resource augmentation for weighted flow-time explained by dual fitting. SODA S. Anand, Naveen Garg, Amit Kumar
2011	J	`jnl`	A 4/3-approximation for TSP on cubic 3-edge-connected graphs CoRR Nishita Aggarwal, Naveen Garg, Swati Gupta
2011	—	`conf`	Meeting Deadlines: How Much Speed Suffices? ICALP (1) S. Anand, Naveen Garg, Nicole Megow
2010	B	`conf`	A 3-Approximation for Facility Location with Uniform Capacities. IPCO Ankit Aggarwal, Anand Louis, Manisha Bansal, Naveen Garg, Neelima Gupta, Shubham Gupta, Surabhi Jain
2010	J	`jnl`	Assigning Papers to Referees. Algorithmica Naveen Garg, Telikepalli Kavitha, Amit Kumar, Kurt Mehlhorn, Julián Mestre
2009	A*	`conf`	A competitive algorithm for minimizing weighted flow time on unrelatedmachines with speed augmentation. STOC Jivitej S. Chadha, Naveen Garg, Amit Kumar, V. N. Muralidhara
2009	—	`conf`	Minimizing Average Flow-Time. Efficient Algorithms Naveen Garg
2008	B	`conf`	Minimizing Total Flow-Time: The Unrelated Case. ISAAC Naveen Garg, Amit Kumar, V. N. Muralidhara
2008	A*	`conf`	Stochastic analyses for online combinatorial optimization problems. SODA Naveen Garg, Anupam Gupta, Stefano Leonardi, Piotr Sankowski
2007	J	`jnl`	Faster and Simpler Algorithms for Multicommodity Flow and Other Fractional Packing Problems. SIAM J. Comput. Naveen Garg, Jochen Könemann
2007	A*	`conf`	Minimizing Average Flow-time: Upper and Lower Bounds. FOCS Naveen Garg, Amit Kumar
2007	—	`conf`	Order Scheduling Models: Hardness and Algorithms. FSTTCS Naveen Garg, Amit Kumar, Vinayaka Pandit
2006	—	`conf`	Better Algorithms for Minimizing Average Flow-Time on Related Machines. ICALP (1) Naveen Garg, Amit Kumar
2006	—	`ed.`	FSTTCS 2006: Foundations of Software Technology and Theoretical Computer Science, 26th International Conference, Kolkata, India, December 13-15, 2006, Proceedings FSTTCS S. Arun-Kumar, Naveen Garg
2006	A*	`conf`	Minimizing average flow time on related machines. STOC Naveen Garg, Amit Kumar
2005	A	`conf`	Heuristic Improvements for Computing Maximum Multicommodity Flow and Minimum Multicut. ESA Garima Batra, Naveen Garg, Garima Gupta
2005	A*	`conf`	Improved approximation for universal facility location. SODA Naveen Garg, Rohit Khandekar, Vinayaka Pandit
2005	—	`conf`	Price of Anarchy, Locality Gap, and a Network Service Provider Game. WINE Nikhil R. Devanur, Naveen Garg, Rohit Khandekar, Vinayaka Pandit, Amin Saberi, Vijay V. Vazirani
2005	A*	`conf`	Saving an epsilon: a 2-approximation for the k-MST problem in graphs. STOC Naveen Garg
2004	A	`conf`	Fractional Covering with Upper Bounds on the Variables: Solving LPs with Negative Entries. ESA Naveen Garg, Rohit Khandekar
2004	J	`jnl`	Local Search Heuristics for k-Median and Facility Location Problems. SIAM J. Comput. Vijay Arya, Naveen Garg, Rohit Khandekar, Adam Meyerson, Kamesh Munagala, Vinayaka Pandit
2004	J	`jnl`	Min-max tree covers of graphs. Oper. Res. Lett. Guy Even, Naveen Garg, Jochen Könemann, R. Ravi, Amitabh Sinha
2004	J	`jnl`	Multiway cuts in node weighted graphs. J. Algorithms Naveen Garg, Vijay V. Vazirani, Mihalis Yannakakis
2003	A*	`conf`	A combinatorial algorithm for computing a maximum independent set in a t-perfect graph. SODA Friedrich Eisenbrand, Stefan Funke, Naveen Garg, Jochen Könemann
2003	A	`conf`	Bandwidth Maximization in Multicasting. ESA Naveen Garg, Rohit Khandekar, Keshav Kunal, Vinayaka Pandit
2003	—	`conf`	Covering Graphs Using Trees and Stars. RANDOM-APPROX Guy Even, Naveen Garg, Jochen Könemann, R. Ravi, Amitabh Sinha
2002	J	`jnl`	Distributed Long-Lived List Colouring: How to Dynamically Allocate Frequencies in Cellular Networks. Wirel. Networks Naveen Garg, Marina Papatriantafilou, Philippas Tsigas
2002	A*	`conf`	Fast Approximation Algorithms for Fractional Steiner Forest and Related Problems. FOCS Naveen Garg, Rohit Khandekar
2002	J	`jnl`	On-Line End-to-End Congestion Control CoRR Naveen Garg, Neal E. Young
2002	A*	`conf`	On-Line End-to-End Congestion Control. FOCS Naveen Garg, Neal E. Young
2001	A*	`conf`	Local search heuristic for k-median and facility location problems. STOC Vijay Arya, Naveen Garg, Rohit Khandekar, Adam Meyerson, Kamesh Munagala, Vinayaka Pandit
2001	B	`conf`	On the Integrality Gap of a Natural Formulation of the Single-Sink Buy-at-Bulk Network Design Problem. IPCO Naveen Garg, Rohit Khandekar, Goran Konjevod, R. Ravi, F. Sibel Salman, Amitabh Sinha II
2000	J	`jnl`	A Polylogarithmic Approximation Algorithm for the Group Steiner Tree Problem. J. Algorithms Naveen Garg, Goran Konjevod, R. Ravi
2000	J	`jnl`	Minimizing stall time in single and parallel disk systems. J. ACM Susanne Albers, Naveen Garg, Stefano Leonardi
1999	—	`conf`	A Randomized Algorithm for Flow Shop Scheduling. FSTTCS Naveen Garg, Sachin Jain, Chaitanya Swamy
1999	J	`jnl`	Finding Separator Cuts in Planar Graphs within Twice the Optimal. SIAM J. Comput. Naveen Garg, Huzur Saran, Vijay V. Vazirani
1999	J	`jnl`	On the Single-Source Unsplittable Flow Problem. Comb. Yefim Dinitz, Naveen Garg, Michel X. Goemans
1998	A*	`conf`	A Polylogarithmic Approximation Algorithm for the Group Steiner Tree Problem. SODA Naveen Garg, Goran Konjevod, R. Ravi
1998	A*	`conf`	Faster and Simpler Algorithms for Multicommodity Flow and Other Fractional Packing Problems. FOCS Naveen Garg, Jochen Könemann
1998	A*	`conf`	Minimizing Stall Time in Single and Parallel Disk Systems. STOC Susanne Albers, Naveen Garg, Stefano Leonardi
1998	A*	`conf`	On the Single-Source Unsplittable Flow Problem. FOCS Yefim Dinitz, Naveen Garg, Michel X. Goemans
1998	J	`jnl`	The Inf. Process. Lett. Shiva Chaudhuri, Naveen Garg, R. Ravi
1997	J	`jnl`	An O (log k)-Approximation Algorithm for the k Minimum Spanning Tree Problem in the Plane. Algorithmica Naveen Garg, Dorit S. Hochbaum
1997	J	`jnl`	Primal-Dual Approximation Algorithms for Integral Flow and Multicut in Trees. Algorithmica Naveen Garg, Vijay V. Vazirani, Mihalis Yannakakis
1996	A*	`conf`	A 3-Approximation for the Minimum Tree Spanning k Vertices. FOCS Naveen Garg
1996	J	`jnl`	Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications. SIAM J. Comput. Naveen Garg, Vijay V. Vazirani, Mihalis Yannakakis
1996	—	`conf`	Distributed List Coloring: How To Dynamically Allocate Frequencies To Mobile Base Stations. SPDP Naveen Garg, Marina Papatriantafilou, Philippas Tsigas
1995	J	`jnl`	A polyhedron with all Math. Program. Naveen Garg, Vijay V. Vazirani
1994	A*	`conf`	A Scaling Technique for Better Network Design. SODA Manica Aggarwal, Naveen Garg
1994	A*	`conf`	An O(log k) approximation algorithm for the k minimum spanning tree problem in the plane. STOC Naveen Garg, Dorit S. Hochbaum
1994	A*	`conf`	Finding separator cuts in planar graphs within twice the optimal FOCS Naveen Garg, Huzur Saran, Vijay V. Vazirani
1994	A*	`conf`	Multiway Cuts in Directed and Node Weighted Graphs. ICALP Naveen Garg, Vijay V. Vazirani, Mihalis Yannakakis
1993	B	`conf`	A polyhedron with all s-t cuts as vertices, and adjacency of cuts. IPCO Naveen Garg, Vijay V. Vazirani
1993	A*	`conf`	Approximate max-flow min-(multi)cut theorems and their applications. STOC Naveen Garg, Vijay V. Vazirani, Mihalis Yannakakis
1993	A*	`conf`	Improved Approximation Algorithms for Biconnected Subgraphs via Better Lower Bounding Techniques. SODA Naveen Garg, Santosh S. Vempala, Aman Singla
1993	A*	`conf`	Primal-Dual Approximation Algorithms for Integral Flow and Multicut in Trees, with Applications to Matching and Set Cover. ICALP Naveen Garg, Vijay V. Vazirani, Mihalis Yannakakis