Mohammad Mahdian
MIT
Abstract: The facility location problem is a central problem in operations research. This problem is extensively studied in the field of approximation algorithms. Numerous approximation algorithms using a variety of techniques have been proposed for this problem. In this talk, I will present three recent algorithms for this problem, designed and analyzed using two new techniques, namely dual-fitting and factor-revealing LPs. One of these algorithms achieves the best known approximation factor for this problme. If time permits, I will also talk about several variants of the facility location problem.
The talk is based on joint works with K. Jain, E. Markakis, A. Saberi, Y. Ye, and J. Zhang