AG Algorithmen und Komplexität

Advanced Algorithmics (SS 15)

NP-hard problems are relevant in practical situations!

Complexity theory tells us that there are problems that seem to be inherently hard to solve. What can we do when faced which such a problem in practice? Over the decades, some useful techniques for tackling hard problems have emerged, for example

  • using heuristics to limit search spaces,
  • accepting wrong outputs with certain probability and
  • accepting suboptimal but still decent solutions.

We follow these approaches and develop theoretical foundations for solving hard problems sufficiently well and fast in practice.

This is an 8 ECTS advanced-level master course; find details in the official documents.


Lectures and exercise sessions will be held throughout the reading period, that is from April 20th to July 24th. Individual sessions will take place weekly on

  • Mondays, 10:00 - 11:30 in 48-654 (lecture),
  • Wednesdays, 10:00 - 11:30 in 48-654 (lecture) and
  • Fridays, 15:30 - 17:00 in 48-654 (exercises)

Note that we will not meet on public holidays, i.e. May 1st and May 25th. We will notify you about replacement dates and other exceptions on a case-by-case basis.


There will be weekly exercise sheets with problems relating to the current lecture material. You can hand in your solutions for grading. We will discuss the exercise problems in weekly exercise sessions, provided sufficient participation. Your TA will be Raphael.

Participation is optional. Register via email to Raphael.


I L1, L2 Sheet 1 Sheet 1, Data
II L3, L4 Sheet 2 Sheet 2
III L5, L6, E1 Sheet 3
IV L7, L8, E2 Sheet 4+ Sheet 3
V L9, L10, E3 Sheet 5 Sheet 4
VI L11, E4 Sheet 6
VII L12, L13, E5 Sheet 7 Sheet 5
VIII L14, E6 Sheet 8
IX L15, L16, E7 Sheet 9
X L17, L18, E8 Sheet 10 Sheet 6
XI L19, L20, E9 Sheet 11
XII L21, L22, E10
XIII L23, E11
XIV E12, E13
* Login required; get credentials from Raphael.
+ Changed after first hand-out.

Find the Git repository used for collaboration on the hands-on sheets here. Please clone the repository and issue pull requests if you want to contribute.


There will be oral exams. Please contact Prof. Nebel towards the end of the lecture period to inquire about possible dates.

Suggested Reading

  • D. Hochbaum: Approximation Algorithms for NP-Hard Problems
    ISBN: 978-0-534-94968-6, available in our library (key text)
  • J. Hromkovič: Algorithmics for Hard Problems
    ISBN: 978-3-642-07909-2, available in our library (key text)
  • V. Vazirani: Approximation Algorithms
    ISBN: 978-3-540-65367-7, available in our library (key text)
  • R. Motwani, P. Raghavan: Randomized Algorithms
    ISBN: 978-0-521-47465-8, available in our library
  • J. Balcazar, J. Diaz, J. Gabarro: Structural Complexity
    ISBN: 978-3-540-58384-4 and 978-3-540-52079-5, available in our library (key text)
  • R. Niedermeier: Invitation to Fixed Parameter Algorithms
    ISBN: 978-0-198-56607-6, available in our library

Prior Iterations

Advanced Algorithmics (SS 13)