Speaker: Chadi Kari
Day:  Wednesday, 04/25/2007
Room: ITEB 336
Time: 2:00-3:30pm

Title: Approximation algorithm for uncapacitated metric facility location

Abstract

One of the most studied problems in the Operations Research literature is
the uncapacitated facility location problem dating back to work in the
early
60's. In its simplest form the problem is as follows: we wish to find
optimal locations to build facilities to serve a given set of clients. Each
client must be assigned to a facility and a cost is incurred that is
proportional to the distance between them. The objective is to determine a
set of locations at which facilities are to be opened so as to minimize the
total facility and assignment costs. This problem is NP-Hard and in recent
years there has been many approximation algorithms and techniques designed
to tackle this problem.  In this talk, an approach based on LP rounding is
discussed.

Reading :

D.B. Shmoys, E. Tardos, and K.I. Aardal, 
"Approximation algorithms for facility location problems," 
in Proceedings of the 29th Annual ACM Symposium on Theory of Computing
(STOC), pages 265--274, 1997.

D. B. Shmoys, 
Approximation algorithms for facility location problems, 
3rd International Workshop on Approximation Algorithms for Combinatorial
Optimization (APPROX), 27-33, 2000.