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)
Abstract:
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.
| 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.