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