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 |

- A regular participation in the talks and an active collaboration are mandatory for passing the seminar.
- The talks will take approximately 75 minutes. The remaining 15 minutes are intended for a discussion.
- Each participant has to write a summary consisting of one or two pages.
- Each participant has to give an approval talk (typically three weeks before the regular talk). Passing the approval talk is a prerequisite for giving the regular seminar talk.

Prof. Dr. B. Korte,

Prof. Dr. J. Vygen,

Prof. Dr. S. Hougardy,

Jun.Prof. Dr. T. Nieberg,

Dr. U. Brenner