max planck institut
mpii logo Minerva of the Max Planck Society

Exponential-Time Algorithms

Basic Information

Lecture time: Fridays 10-12
Lecture room: E1.4 Room 0.24
Lecturer: Matthias Mnich
Tutorial time: Thursdays 2-4pm
Tutorial room: Building E1 7, Room 3.23 (except May 10: Building E1 4, Rotunde 2nd floor)
Tutor: Megha Khosla
Audience: The course counts as computer science lecture (2 SWS, 6 CP). The lecture will be given in English.

Information: The first lecture will take place on Friday, April 20th.
Exercises: We will hand out exercises every week. For admission for the final exam, you have to (1) achieve at least 40% of the possible points and (2) present a solution at least twice in a tutorial. The points in the exercises do NOT count towards the final grade of the exam.
Final Exam Date: 27 July 2012, 12pm - 2pm, Room 0.24 in Building E1 4.
Re-Exam Date: to be determined
Reference books: Most of the course material is covered in Fedor Fomin and Dieter Kratsch: Exact Exponential Algorithms


Many fundamental problems in theoretical computer science have been classified as "intractable", meaning that no "efficient" algorithm to solve them is known or likely to exist. As this is no excuse for not solving these problems, algorithms have been designed that produce solutions of different qualities, compared to an optimal solution. Popular kinds of algorithms for intractable problems are heuristics, that aim for good-quality solutions for instances occurring in practice but for which no such quality can be guaranteed, and approximation algorithms, that produce solutions for which the ratio between the quality of a produced solution and an optimal solution can be bounded, for all possible instances. Both kinds of algorithms are efficient, that is, the time required by them to produce a solution is bounded by a polynomial in the size of the input instance. Another kind of algorithms for intractable problems is the topic of this course: exponential-time algorithms, that always return an optimal solution for any instance. Our objective is to design exponential-time algorithms running in time that is "moderate" for instances of relatively small size. That means, their time requirement is provably (and desirably significantly) less than that of exhaustively searching through all feasible solutions for an optimal one. With this course we aim to give an introduction into this very active area of research.


Date Topic Reference
Apr 20 Introduction, Motivation, Examples Woeginger: Exact Algorithms for NP-hard Problems: A survey

Apr 27 Branching algorithms, bounded search trees Kullmann: Fundamentals of Branching Heuristics

May 4 Measure and Conquer Fomin, Grandoni, Kratsch: A measure & conquer approach for the analysis of exact algorithms.

May 11 Dynamic Programming Bodlaender, Fomin, Koster, Kratsch: A note on exact algorithms for vertex ordering problems on graphs

May 18 Dynamic Programming Continued Qiang-Sheng Hua, Yuexuan Wang, Dongxiao Yu, Francis C. M. Lau: Dynamic programming based algorithms for set multicover and multiset multicover problems

May 25 Split and List Ryan Williams: A new algorithm for optimal 2-constraint satisfaction and its implications

June 1 Local Search Tobias Brüggemann and Walter Kern: An improved local search algorithm for 3SAT

June 8 Max Cut Revisited Serge Gaspers and Gregory B. Sorkin: A universally fastest algorithm for Max 2-Sat, Max 2-CSP, and everything in between

June 15 (no lecture)

June 22 The Principle of Inclusion-Exclusion Thore Husfeldt: Invitation to Algorithmic Uses of Inclusion-Exclusion

June 29 (no lecture)

July 6 Fast Subset Convolution Andreas Björklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto: Fourier meets Möbius: fast subset convolution

July 13 Partitioning Problems Mikko Koivisto: Partitioning into sets of bounded cardinality

July 20 Last Lecture

Results of final exam

More Courses of the Algorithms and Complexity Group
Search MPII (type ? for help)