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.
|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|