Tata Institute of Fundamental Research

Capacitated Facility Location with Outliers

STCS Seminar
Speaker: Naveen Garg (Indian Institute of Technology Delhi)
Organiser: Raghuvansh Saxena
Date: Tuesday, 9 Apr 2024, 16:00 to 17:00
Venue: via Zoom in A201

(Scan to add to calendar)

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.