![](https://dblp.dagstuhl.de/img/logo.ua.320x120.png)
![](https://dblp.dagstuhl.de/img/dropdown.dark.16x16.png)
![](https://dblp.dagstuhl.de/img/peace.dark.16x16.png)
Остановите войну!
for scientists:
![search dblp search dblp](https://dblp.dagstuhl.de/img/search.dark.16x16.png)
![search dblp](https://dblp.dagstuhl.de/img/search.dark.16x16.png)
default search action
Naveen Garg 0001
Person information
- affiliation: Indian Institute of Technology Delhi, India
- affiliation (former): Max Planck Institute for Informatics, Saarbrücken, Germany
Other persons with the same name
- Naveen Garg — disambiguation page
- Naveen Garg 0002
— University of Texas, MD Anderson Cancer Center, Houston, TX, USA
Refine list
![note](https://dblp.dagstuhl.de/img/note-mark.dark.12x12.png)
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
2020 – today
- 2024
- [c53]Rajni Dabas
, Naveen Garg, Neelima Gupta:
Capacitated Facility Location with Outliers and Uniform Facility Costs. IPCO 2024: 85-98 - [i10]Rohith Reddy Gangam, Naveen Garg, Parnian Shahkar, Vijay V. Vazirani:
The Flow Game: Leximin and Leximax Core Imputations. CoRR abs/2403.06037 (2024) - 2023
- [j22]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): S18-158 (2023) - 2022
- [j21]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: 111-142 (2022) - [j20]Naveen Garg
, Nikhil Kumar, András Sebö:
Integer plane multiflow maximisation: one-quarter-approximation and gaps. Math. Program. 195(1): 403-419 (2022) - [c52]Rajni Dabas, Naveen Garg, Neelima Gupta, Dilpreet Kaur:
Locating Service and Charging Stations. WAOA 2022: 1-19 - 2021
- [c51]Naveen Garg, Sanjeev Khanna, Amit Kumar:
Hardness of Approximation for Orienteering with Multiple Time Windows. SODA 2021: 2977-2990 - 2020
- [c50]Naveen Garg
, Nikhil Kumar:
Dual Half-Integrality for Uncrossable Cut Cover and Its Application to Maximum Half-Integral Flow. ESA 2020: 55:1-55:13 - [c49]Naveen Garg
, Nikhil Kumar, András Sebö:
Integer Plane Multiflow Maximisation: Flow-Cut Gap and One-Quarter-Approximation. IPCO 2020: 144-157 - [c48]Antonios Antoniadis, Naveen Garg, Gunjan Kumar, Nikhil Kumar:
Parallel Machine Scheduling to Minimize Energy Consumption. SODA 2020: 2758-2769 - [i9]Naveen Garg, Nikhil Kumar, András Sebö:
Integer Plane Multiflow Maximisation: Flow-Cut Gap and One-Quarter-Approximation. CoRR abs/2002.10927 (2020) - [i8]Naveen Garg, Nikhil Kumar:
Dual Half-integrality for Uncrossable Cut Cover and its Application to Maximum Half-Integral Flow. CoRR abs/2007.14156 (2020)
2010 – 2019
- 2019
- [c47]Naveen Garg
, Anupam Gupta, Amit Kumar
, Sahil Singla:
Non-Clairvoyant Precedence Constrained Scheduling. ICALP 2019: 63:1-63:14 - [i7]Naveen Garg, Anupam Gupta, Amit Kumar, Sahil Singla:
Non-clairvoyant Precedence Constrained Scheduling. CoRR abs/1905.02133 (2019) - [i6]Antonios Antoniadis, Naveen Garg, Gunjan Kumar, Nikhil Kumar:
Parallel Machine Scheduling to Minimize Energy Consumption. CoRR abs/1909.13345 (2019) - 2018
- [j19]Anamitra Roy Choudhury, Syamantak Das, Naveen Garg
, Amit Kumar
:
Rejecting jobs to minimize load and maximum flow-time. J. Comput. Syst. Sci. 91: 42-68 (2018) - [j18]Nishita Agarwal, Naveen Garg
, Swati Gupta:
A 4/3-approximation for TSP on cubic 3-edge-connected graphs. Oper. Res. Lett. 46(4): 393-396 (2018) - [c46]Jatin Batra, Naveen Garg
, Amit Kumar
:
Constant Factor Approximation Algorithm for Weighted Flow Time on a Single Machine in Pseudo-Polynomial Time. FOCS 2018: 778-789 - [c45]Manisha Bansal
, Naveen Garg
, Neelima Gupta:
A 5-Approximation for Universal Facility Location. FSTTCS 2018: 24:1-24:12 - [c44]Bhaskar Ray Chaudhury, Yun Kuen Cheung, Jugal Garg, Naveen Garg
, Martin Hoefer, Kurt Mehlhorn:
On Fair Division for Indivisible Items. FSTTCS 2018: 25:1-25:17 - [i5]Jatin Batra, Naveen Garg, Amit Kumar:
Constant Factor Approximation Algorithm for Weighted Flow Time on a Single Machine in Pseudo-polynomial time. CoRR abs/1802.07439 (2018) - [i4]Yun Kuen Cheung, Bhaskar Chaudhuri, Jugal Garg, Naveen Garg, Martin Hoefer, Kurt Mehlhorn:
On Fair Division of Indivisible Items. CoRR abs/1805.06232 (2018) - 2017
- [j17]S. Anand, Karl Bringmann, Tobias Friedrich, Naveen Garg
, Amit Kumar:
Minimizing Maximum (Weighted) Flow-Time on Related and Unrelated Machines. Algorithmica 77(2): 515-536 (2017) - 2015
- [c43]Jatin Batra, Naveen Garg
, Amit Kumar
, Tobias Mömke, Andreas Wiese
:
New Approximation Schemes for Unsplittable Flow on a Path. SODA 2015: 47-58 - [c42]Anamitra Roy Choudhury, Syamantak Das, Naveen Garg
, Amit Kumar
:
Rejecting jobs to Minimize Load and Maximum Flow-time. SODA 2015: 1114-1133 - [e2]Naveen Garg, Klaus Jansen, Anup Rao, José D. P. Rolim:
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2015, August 24-26, 2015, Princeton, NJ, USA. LIPIcs 40, Schloss Dagstuhl - Leibniz-Zentrum für Informatik 2015, ISBN 978-3-939897-89-7 [contents] - 2014
- [i3]Anamitra Roy Choudhury, Syamantak Das, Naveen Garg, Amit Kumar:
Rejecting Jobs to Minimize Load and Maximum Flow-time. CoRR abs/1410.1839 (2014) - 2013
- [j16]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): 527-547 (2013) - [c41]S. Anand, Karl Bringmann, Tobias Friedrich, Naveen Garg
, Amit Kumar
:
Minimizing Maximum (Weighted) Flow-Time on Related and Unrelated Machines. ICALP (1) 2013: 13-24 - 2012
- [c40]Manisha Bansal
, Naveen Garg
, Neelima Gupta:
A 5-Approximation for Capacitated Facility Location. ESA 2012: 133-144 - [c39]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: 267-275 - [c38]S. Anand, Naveen Garg
, Amit Kumar
:
Resource augmentation for weighted flow-time explained by dual fitting. SODA 2012: 1228-1241 - 2011
- [c37]S. Anand, Naveen Garg
, Nicole Megow
:
Meeting Deadlines: How Much Speed Suffices? ICALP (1) 2011: 232-243 - [i2]Nishita Aggarwal, Naveen Garg, Swati Gupta:
A 4/3-approximation for TSP on cubic 3-edge-connected graphs. CoRR abs/1101.5586 (2011) - 2010
- [j15]Naveen Garg
, Telikepalli Kavitha, Amit Kumar
, Kurt Mehlhorn, Julián Mestre:
Assigning Papers to Referees. Algorithmica 58(1): 119-136 (2010) - [c36]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: 149-162
2000 – 2009
- 2009
- [c35]Naveen Garg
:
Minimizing Average Flow-Time. Efficient Algorithms 2009: 187-198 - [c34]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: 679-684 - 2008
- [c33]Naveen Garg
, Amit Kumar
, V. N. Muralidhara:
Minimizing Total Flow-Time: The Unrelated Case. ISAAC 2008: 424-435 - [c32]Naveen Garg, Anupam Gupta, Stefano Leonardi, Piotr Sankowski:
Stochastic analyses for online combinatorial optimization problems. SODA 2008: 942-951 - 2007
- [j14]Naveen Garg
, Jochen Könemann:
Faster and Simpler Algorithms for Multicommodity Flow and Other Fractional Packing Problems. SIAM J. Comput. 37(2): 630-652 (2007) - [c31]Naveen Garg, Amit Kumar:
Minimizing Average Flow-time : Upper and Lower Bounds. FOCS 2007: 603-613 - [c30]Naveen Garg
, Amit Kumar, Vinayaka Pandit:
Order Scheduling Models: Hardness and Algorithms. FSTTCS 2007: 96-107 - 2006
- [c29]Naveen Garg
, Amit Kumar:
Better Algorithms for Minimizing Average Flow-Time on Related Machines. ICALP (1) 2006: 181-190 - [c28]Naveen Garg
, Amit Kumar
:
Minimizing average flow time on related machines. STOC 2006: 730-738 - [e1]S. Arun-Kumar, Naveen Garg:
FSTTCS 2006: Foundations of Software Technology and Theoretical Computer Science, 26th International Conference, Kolkata, India, December 13-15, 2006, Proceedings. Lecture Notes in Computer Science 4337, Springer 2006, ISBN 3-540-49994-6 [contents] - 2005
- [c27]Garima Batra, Naveen Garg
, Garima Gupta:
Heuristic Improvements for Computing Maximum Multicommodity Flow and Minimum Multicut. ESA 2005: 35-46 - [c26]Naveen Garg, Rohit Khandekar, Vinayaka Pandit:
Improved approximation for universal facility location. SODA 2005: 959-960 - [c25]Naveen Garg
:
Saving an epsilon: a 2-approximation for the k-MST problem in graphs. STOC 2005: 396-402 - [c24]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: 1046-1055 - 2004
- [j13]Naveen Garg
, Vijay V. Vazirani, Mihalis Yannakakis:
Multiway cuts in node weighted graphs. J. Algorithms 50(1): 49-61 (2004) - [j12]Guy Even, Naveen Garg
, Jochen Könemann, R. Ravi, Amitabh Sinha:
Min-max tree covers of graphs. Oper. Res. Lett. 32(4): 309-315 (2004) - [j11]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): 544-562 (2004) - [c23]Naveen Garg
, Rohit Khandekar:
Fractional Covering with Upper Bounds on the Variables: Solving LPs with Negative Entries. ESA 2004: 371-382 - 2003
- [c22]Naveen Garg
, Rohit Khandekar, Keshav Kunal, Vinayaka Pandit:
Bandwidth Maximization in Multicasting. ESA 2003: 242-253 - [c21]Guy Even, Naveen Garg
, Jochen Könemann, R. Ravi, Amitabh Sinha:
Covering Graphs Using Trees and Stars. RANDOM-APPROX 2003: 24-35 - [c20]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: 517-522 - 2002
- [j10]Naveen Garg
, Marina Papatriantafilou
, Philippas Tsigas
:
Distributed Long-Lived List Colouring: How to Dynamically Allocate Frequencies in Cellular Networks. Wirel. Networks 8(1): 49-60 (2002) - [c19]Naveen Garg, Neal E. Young
:
On-Line End-to-End Congestion Control. FOCS 2002: 303-312 - [c18]Naveen Garg, Rohit Khandekar:
Fast Approximation Algorithms for Fractional Steiner Forest and Related Problems. FOCS 2002: 500- - [i1]Naveen Garg, Neal E. Young:
On-Line End-to-End Congestion Control. CoRR cs.DS/0205032 (2002) - 2001
- [c17]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: 170-184 - [c16]Vijay Arya, Naveen Garg, Rohit Khandekar, Adam Meyerson, Kamesh Munagala, Vinayaka Pandit:
Local search heuristic for k-median and facility location problems. STOC 2001: 21-29 - 2000
- [j9]Susanne Albers, Naveen Garg
, Stefano Leonardi:
Minimizing stall time in single and parallel disk systems. J. ACM 47(6): 969-986 (2000) - [j8]Naveen Garg
, Goran Konjevod
, R. Ravi:
A Polylogarithmic Approximation Algorithm for the Group Steiner Tree Problem. J. Algorithms 37(1): 66-84 (2000)
1990 – 1999
- 1999
- [j7]Yefim Dinitz, Naveen Garg
, Michel X. Goemans:
On the Single-Source Unsplittable Flow Problem. Comb. 19(1): 17-41 (1999) - [j6]Naveen Garg
, Huzur Saran, Vijay V. Vazirani:
Finding Separator Cuts in Planar Graphs within Twice the Optimal. SIAM J. Comput. 29(1): 159-179 (1999) - [c15]Naveen Garg
, Sachin Jain, Chaitanya Swamy:
A Randomized Algorithm for Flow Shop Scheduling. FSTTCS 1999: 213-218 - 1998
- [j5]Shiva Chaudhuri, Naveen Garg
, R. Ravi:
The p-Neighbor k-Center Problem. Inf. Process. Lett. 65(3): 131-134 (1998) - [c14]Yefim Dinitz, Naveen Garg, Michel X. Goemans:
On the Single-Source Unsplittable Flow Problem. FOCS 1998: 290-299 - [c13]Naveen Garg, Jochen Könemann:
Faster and Simpler Algorithms for Multicommodity Flow and Other Fractional Packing Problems. FOCS 1998: 300-309 - [c12]Naveen Garg, Goran Konjevod, R. Ravi:
A Polylogarithmic Approximation Algorithm for the Group Steiner Tree Problem. SODA 1998: 253-259 - [c11]Susanne Albers, Naveen Garg
, Stefano Leonardi:
Minimizing Stall Time in Single and Parallel Disk Systems. STOC 1998: 454-462 - 1997
- [j4]Naveen Garg
, Vijay V. Vazirani, Mihalis Yannakakis:
Primal-Dual Approximation Algorithms for Integral Flow and Multicut in Trees. Algorithmica 18(1): 3-20 (1997) - [j3]Naveen Garg
, Dorit S. Hochbaum:
An O (log k)-Approximation Algorithm for the k Minimum Spanning Tree Problem in the Plane. Algorithmica 18(1): 111-121 (1997) - 1996
- [j2]Naveen Garg
, Vijay V. Vazirani, Mihalis Yannakakis:
Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications. SIAM J. Comput. 25(2): 235-251 (1996) - [c10]Naveen Garg:
A 3-Approximation for the Minimum Tree Spanning k Vertices. FOCS 1996: 302-309 - [c9]Naveen Garg, Marina Papatriantafilou, Philippas Tsigas:
Distributed List Coloring: How To Dynamically Allocate Frequencies To Mobile Base Stations. SPDP 1996: 18-25 - 1995
- [j1]Naveen Garg
, Vijay V. Vazirani:
A polyhedron with alls - t cuts as vertices, and adjacency of cuts. Math. Program. 70: 17-25 (1995) - 1994
- [c8]Naveen Garg, Huzur Saran, Vijay V. Vazirani:
Finding separator cuts in planar graphs within twice the optimal. FOCS 1994: 14-23 - [c7]Naveen Garg
, Vijay V. Vazirani, Mihalis Yannakakis:
Multiway Cuts in Directed and Node Weighted Graphs. ICALP 1994: 487-498 - [c6]Manica Aggarwal, Naveen Garg:
A Scaling Technique for Better Network Design. SODA 1994: 233-240 - [c5]Naveen Garg
, Dorit S. Hochbaum:
An O(log k) approximation algorithm for the k minimum spanning tree problem in the plane. STOC 1994: 432-438 - 1993
- [c4]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: 64-75 - [c3]Naveen Garg, Vijay V. Vazirani:
A polyhedron with all s-t cuts as vertices, and adjacency of cuts. IPCO 1993: 281-289 - [c2]Naveen Garg, Santosh S. Vempala, Aman Singla:
Improved Approximation Algorithms for Biconnected Subgraphs via Better Lower Bounding Techniques. SODA 1993: 103-111 - [c1]Naveen Garg
, Vijay V. Vazirani, Mihalis Yannakakis:
Approximate max-flow min-(multi)cut theorems and their applications. STOC 1993: 698-707
Coauthor Index
![](https://dblp.dagstuhl.de/img/cog.dark.24x24.png)
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
Unpaywalled article links
Add open access links from to the list of external document links (if available).
Privacy notice: By enabling the option above, your browser will contact the API of unpaywall.org to load hyperlinks to open access articles. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Unpaywall privacy policy.
Archived links via Wayback Machine
For web page which are no longer available, try to retrieve content from the of the Internet Archive (if available).
Privacy notice: By enabling the option above, your browser will contact the API of archive.org to check for archived content of web pages that are no longer available. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Internet Archive privacy policy.
Reference lists
Add a list of references from ,
, and
to record detail pages.
load references from crossref.org and opencitations.net
Privacy notice: By enabling the option above, your browser will contact the APIs of crossref.org, opencitations.net, and semanticscholar.org to load article reference information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Crossref privacy policy and the OpenCitations privacy policy, as well as the AI2 Privacy Policy covering Semantic Scholar.
Citation data
Add a list of citing articles from and
to record detail pages.
load citations from opencitations.net
Privacy notice: By enabling the option above, your browser will contact the API of opencitations.net and semanticscholar.org to load citation information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the OpenCitations privacy policy as well as the AI2 Privacy Policy covering Semantic Scholar.
OpenAlex data
Load additional information about publications from .
Privacy notice: By enabling the option above, your browser will contact the API of openalex.org to load additional information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the information given by OpenAlex.
last updated on 2024-06-19 21:04 CEST by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint