Facility location problems occur in various applications. Generally spoken, they deal with finding an optimum number and locations of certain central institutions in order to satisfy customer needs in a most efficient way. One asks for an optimum balance of facility costs that are incurred with each extra facility, and service costs which depend on the distance of each customer to his or her nearest facility. Often, facilities have limited capacity and can thus serve only some of the customers.
Almost all variants of the problem are NP-hard. However, in the last decade many different approximation algorithms have been found. The most recent algorithms combine a good performance guarantee with an efficient running time, and some of them apply to a quite general context. We will review several of these algorithms in detail. The techniques will include linear programming, greedy, primal-dual, and local search.
Topics: 1) The Fermat-Weber problem; 2) Weiszfeld's algorithm; 3) The Uncapacitated Facility Location Problem; 4) LP rounding algorithms (Shmoys, Tardos, Aardal; Chudak, Shmoys); 5) primal-dual algorithms (Jain, Vazirani); 6) greedy augmentation (Charikar, Guha); 7) advanced primal-dual algorithms and factor-revealing LPS (Mahdian et al.); 8) lower bound on approximation ratio (Guha, Khuller); 9) Lagrangean relaxation for k-median and soft capacities (Jain, Vazirani); 10) local search algorithms (Arya et al.); 11) universal facility locationi (Mahdian, Pal).
This lecture is given in English. So far there is no book or survey text that can be recommended as most results are very new. However, I am composing lecture notes which are distributed to the students.
Prerequisites: | basics of linear programming, graph theory, discrete algorithms, combinatorial optimization (for example, one of the lectures Diskrete Mathematik / Mathematische Optimierung will usually suffice). However, it will be possible (though a bit more difficult) to follow the lecture with Vordiplom only. | |
Venue: | Gerhard-Konow-Hörsaal (Lennéstr. 2) | |
Time: | Tuesdays 12:15 - 13:45 p.m. |
Professor Dr. J. Vygen