First Meeting: 19th October, 2023, 2 pm, A7/SR 031 

Welcome :: Overview slides

Highlights of approximation algorithms

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 (e.g. ALP3/HA) and general knowledge (e.g. basics of graph theory, Big-O-notation, etc.) and mathematical maturity is assumed.

Tentative schedule and topic selection

(detailes to be concretized as we go)

Nov. 9.  -- Matthias Kupferschmidt -- deterministic LP rounding

Nov. 16. -- Jakub Tarka -- dynamic programming and data rounding

Nov. 23. -- LK -- more LP-based techniques/examples

Nov. 30. -- Nils Seitz -- shortest superstring [report]

Dec. 7. --  Niklas Rosseck -- primal/dual

Dec. 14. -- Jatin Kansal -- cuts and metrics

Jan. 11. -- Mouadh Khlifi -- greedy and local search

Jan. 18. -- Moslem Afrasiabi -- Scheduling, bin packing and

Jan. 25. -- Jakob Knitter: randomized sampling/rounding
              -- Tolga Yurtseven: PTAS for TSP

Jan. 31.  -- Manuel Welte: SDP relaxation