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. However, in the last decade 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.
A more detailed syllabus will be published here later, probably in October.
I plan to give this lecture in English. So far there is no book or survey text that can be recommended as most results are very new. However, I plan to compose lecture notes, which will be distributed to the students.
| Prerequisites: | basics of linear programming, graph theory, discrete algorithms, combinatorial optimization (for example, one of the lectures Diskrete Mathematik / Mathematische Optimierung will usually suffice). However, it will be possible (though a bit more difficult) to follow the lecture with Vordiplom only. | |
| Venue: | Gerhard-Konow-Hörsaal (Lennéstr. 2) | |
| Time: | Tuesdays 12:15 - 13:45 p.m. |
Prof. Dr. J. Vygen