AG Algorithmen und Komplexität

Advanced Algorithmics (SS 13)

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 (INF-54-54-V-7).


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

  • Wednesdays, 10:00 - 11:30 in 48-654 (lecture),
  • Wednesdays, 13:45 - 15:15 in 48-654 (exercises) and
  • Thursdays, 10:00 - 11:30 in 48-654 (lecture).

Note that we will not meet on public holidays, i.e. May 1st, May 9th, May 30th.


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 in the first lecture or via email to Raphael.


I L1 Sheet 1 Sheet 1, Data
II L2, L3* Sheet 2+ Sheet 2
III L4 Sheet 3  
IV L5 Sheet 4+  
V L6, L7 Sheet 5+ Sheet 3
VI L8, L9 Sheet 6 Sheet 4
VII L10 Sheet 7  
VIII L11, L12 Sheet 8+ Sheet 5
IX L13*, L14 Sheet 9+  
X L15*, L16* Sheet 10  
XI L17, L18 Sheet 11  
XII L19, L20 Sheet 12  
XIII L21, L22 Session 11  
XIV L23   Sheet 06

* There have been changes since the lecture.
+ There have been changes since hand-in.

Lecture slides are only available for logged in users; please use the credentials given to you in class.


Examination procedure will be announced in the first lecture.

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