Naveen Garg

About

Naveen Garg is the Usha Hasteer Chair of Computer Science at IIT Delhi. He earned his BTech & PhD from IIT Delhi and was a postdoctoral fellow at MPI Informatik. He designs approximation algorithms for NP-hard combinatorial optimisation problems arising in network design, scheduling, routing and facility location. He is a Fellow of the Indian Academy of Science and the Indian National Academy of Engineering and received the Friderich-Wilhelm-Bessel Prize (2002) and the SS Bhatnagar Award (2016).

Employment

• Indian Institute of Technology Delhi Professor
  2007 - Present
• Indian Institute of Technology Delhi Associate Professor
  2000 - 2007
• Indian Institute of Technology Delhi Assistant Professor
  1997 - 2000
• Max-Planck-Institut für Informatik Wissenchaftler Mitarbeiter
  1996 - 1997
• Max-Planck-Institut für Informatik Postdoctoral fellow
  1994 - 1996

Education

• Indian Institute of Technology Delhi PhD
  1991 - 1994
• Indian Institute of Technology Delhi Bachelor of Technology
  1987 - 1991

Projects & Funding

Projects & funding information is unavailable.

Publications (72)

• The Online Piercing Set Problem with Recourse
  2026 DOI: 10.1007/978-3-032-06706-7_2
  +Save
• Integer plane multiflow maximisation: one-quarter-approximation and gaps
  Mathematical Programming 2022 DOI: 10.1007/s10107-021-01700-8
  +Save
• Integer Plane Multiflow Maximisation: Flow-Cut Gap and One-Quarter-Approximation
  Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 2020 DOI: 10.1007/978-3-030-45771-6_12
  +Save
• Parallel machine scheduling to minimize energy consumption
  Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms 2020
  +Save
• Dual half-integrality for uncrossable cut cover and its application to maximum half-integral flow
  Leibniz International Proceedings in Informatics, LIPIcs 2020 DOI: 10.4230/LIPIcs.ESA.2020.55
  +Save
• Non-clairvoyant precedence constrained scheduling
  Leibniz International Proceedings in Informatics, LIPIcs 2019 DOI: 10.4230/LIPIcs.ICALP.2019.63
  +Save
• A 4/3-approximation for TSP on cubic 3-edge-connected graphs
  Operations Research Letters 2018 DOI: 10.1016/j.orl.2018.04.007
  +Save
• A 5-approximation for universal facility location
  Leibniz International Proceedings in Informatics, LIPIcs 2018 DOI: 10.4230/LIPIcs.FSTTCS.2018.24
  +Save
• Constant factor approximation algorithm for weighted flow time on a single machine in pseudo-polynomial time
  Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS 2018 DOI: 10.1109/FOCS.2018.00079
  +Save
• On fair division for indivisible items
  Leibniz International Proceedings in Informatics, LIPIcs 2018 DOI: 10.4230/LIPIcs.FSTTCS.2018.25
  +Save