Research Institute for Discrete Mathematics

Lecture Course "Facility Location Problems" (V5C2)

Winter Term 2012/2013

In facility location problems, the task is to choose a set of facilities that have to supply a given set of customers. There is an opening cost for establishing a facility and a service cost for assigning a certain customer to a facility.

Obviously, such problems have important applications in logistics where facilities can be, e.g., warehouses, stores, or hospitals. However, there are as well applications, for example, in the context of VLSI chip design.

Though facility location problems have been studied for decades, some fifteen years ago no approximation algorithm was known for any variant of them. Since then, several approximation algorithms have been found, and, on the other hand, non-approximability results have been improved. In this lecture we will study both algorithms and hardness results for different types of facility location problems.

This lecture course is part of the Master's Program in Mathematics.

Prerequisites: Knowledge about basic results in complexity theory, approximation algorithms, and linear and integer programming (as presented e.g. in the lecture courses "Einführung in die Diskrete Mathematik" and "Lineare und ganzzahlige Optimierung" of the Bachelor's Program Mathematics).

Class Hours: Tuesdays 10 am - 12 pm (10:15-11:45)
Room: Gerhard-Konow-Hörsaal (in the Arithmeum building, Lennéstr. 2)

Dr. U. Brenner