Seminar on Approximation Algorithms (Winter 2025/26)

Some of the most important optimization problems that arise in practice are NP-hard, and thus we cannot hope to solve them exactly for all inputs. In many applications approximate solutions are acceptable, and approximations with provable guarantees are preferred. Example problems include the traveling salesman (TSP), scheduling, packing, covering, and network design.

In this seminar we overview some classical and new approximation results, with the aim to learn general design and analysis techniques: greedy, local search, LP-based techniques, etc. The topics will be based on selected chapters from textbooks and research articles.

The seminar is open to all students interested in algorithms and theoretical computer science. Some algorithmic background and general mathematical maturity is expected.

The first meeting is on Wednesday, October 22, 1 pm, in APB/E3027. All further meetings will be scheduled according to the availability of the participants.

Introductory slides of the first meeting, with information about topics and organization.

Tentative schedule:

Kontakt

• Prof. Dr. László Kozma
  Tel.: +49 (0) 351 463-38232