Campus Event Calendar

Event Entry

What and Who

Outliers: How to Handle Them

Naveen Garg
IIT Delhi

Naveen Garg is the Janaki and K. A. Iyer Chair Professor of Computer Science at the Indian
Institute of Technology Delhi. He did his B.Tech. and Ph.D. in Computer Science from IIT Delhi,
was a postdoctoral researcher at the Max-Planck-Institut fur Informatik, Germany and since
1998 he has been a faculty member at IIT Delhi.
Naveen’s contributions are primarily in the design and analysis of approximation algorithms for
NP-hard combinatorial optimization problems arising in network design, scheduling, routing,
facility location etc. He is a Fellow of Indian Academy of Science, Bangalore and was awarded
the SS Bhatnagar award for Mathematical Sciences in 2016
AG 1, INET, AG 5, RG1, SWS, AG 2, AG 4, D6, AG 3  
AG Audience

Date, Time and Location

Friday, 10 February 2023
45 Minutes


Title: Outliers: How to handle them
Abstract: Handling clients which are outliers in facility location problems is a challenging task. For the capacitated facility location problem with uniform facility costs and outliers, we provide the first constant factor approximation. Our local search algorithm uses only 2 operations and yields a 6.372 approximation. In developing this algorithm we give a new and improved algorithm for capacitated facility location with uniform facility costs. Our local search algorithm is a 3.732 approximation and improves on the 4.562 approximation of Aardal More importantly, it is simple to state and analyse.


Kurt Mehlhorn
+49 681 9325 1025
--email hidden
passcode not visible

Kurt Mehlhorn, 01/31/2023 09:02 -- Created document.