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-approximation of Kao. More importantly, it is simple
to state and analyse.
Speaker Bio
Naveen Garg is the Janaki and K. A. Iyer 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, the Indian National Academy of Engineering, Delhi and was awarded the SS Bhatnagar award for Mathematical Sciences in 2016.