In this talk I will present a simple local search algorithm for capacitated facility location when facility costs are uniform. Our algorithm is a 3.732-approximation and improves the 4-approximation of Kao.
In the second part of the talk, I will consider the setting when we are permitted not to serve L clients (outliers). We extend the local search algorithm to obtain the first constant factor approximation for this problem. Our local search algorithm requires only 2 operations and is a 6.372-approximation.
Short Bio:
Naveen Garg is the Usha Hasteer 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. He is currently on a sabbatical at the University of Warwick, UK as a Royal Society Wolfson visiting professor.
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, and the Indian National Academy of Engineering and was awarded the SS Bhatnagar award for Mathematical Sciences in 2016.
