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   Info

AG Audience

English

45 Minutes

Saarbrücken

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 et.al. More importantly, it is simple to state and analyse.

Kurt Mehlhorn

+49 681 9325 1025

--email hidden