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