Forschungsinstitut für Diskrete Mathematik

Graduate Seminar on Discrete Optimization (S4C1)

Summer 2009

Facility Location Problems

Class hours: Mondays 14:15-15:45; Approval talks: Mondays 12:30-14:00

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. Up to 1997, no approximations were known. However, since then 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. Chapter 22 of the book Combinatorial Optimization: Theory and Algorithms by B. Korte and J. Vygen (Springer, fourth edition 2008) serves as a good introduction.

Number Approval talk Talk Name Topic Mentoring
1 14.4.
20.4. Niko Klewinghaus Introduction (Hochbaum, 1982) Christian Schulte
2 14.4.
27.4. Arne Gewert LP Rounding (Shmoys-Tardos-Aardal, 1997, Chudak-Shmoys, 2003) Ulrich Brenner
3 20.4.
4.5. Martin Montag Greedy algorithm an inapproximability (Guha-Khuller, 1999) Christian Schulte
4 27.4.
11.5. Julian Iseringhausen Primal-Dual (Jain-Vazirani, 2001) Jan Schneider
5 4.5.
18.5. Helmut Grohne Scaling and greedy augmentation (Charikar-Guha, 2005) Stephan Held
6 11.5.
25.5. Aylin Ilhan Dual fitting algorithm (Jain et al., 2003) Stephan Held
7 18.5.
8.6. Sophie Küster 1.5-approximation (Byrka, 2007) Markus Struzyna
8 25.5.
15.6. Ali Iftikhar Local search (Arya et al., 2004) Markus Struzyna
9 8.6.
22.6. Alexander Renelt Capacitated facility location (Zhang-Chen-Ye, 2005) Markus Struzyna
10 15.6.
29.6. Tobias Gödderz Universal facility location (Vygen, 2007) Christian Schulte
11 22.6.
6.7. Thomas Petig Facility location with service capacities (Maßberg-Vygen, 2008) Jens Maßberg
12 29.6.
13.7. Cornelius Dirk Connected facility location (Eisenbrand et al., 2008) Jan Schneider
13 6.7.
20.7. Jan Zernisch Multilevel facility location (Aardal-Chudak-Chmoys, 1999, Ageev-Ye-Zhang, 2003) Christoph Bartoschek

Prof. Dr. B. Korte,
Prof. Dr. J. Vygen,
Prof. Dr. S. Hougardy,
Jun.Prof. Dr. T. Nieberg,
Dr. U. Brenner