Forschungsinstitut für Diskrete Mathematik

Facility Location Problems

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.

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