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.

Important: coordinate choice of topic and presentation timeslot in e-mail until 5th Nov.

Tentative schedule: (Topics with no student name are still available; presentation dates to be fixed a bit later.)

Kontakt

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