Dr. Tobias Mömke
Dr. Hang Zhou
NewsPlease register for the course.
If you cannot attend the exercise class, please consider to visit Daniel Vaz at his office hours to discuss your solutions.Electronic versions of the course literature are freely available online:
Given an NP-hard optimization problem, how well can it be approximated in polynomial time? It is exciting and challenging to understand the approximability of fundamental optimization problems. This course mainly focuses on upper bounds, i.e., designing efficient approximation algorithms.
In this course, we will study several classes of problems, such as packing problems, network design, and graph problems. We will cover central algorithmic techniques for designing approximation algorithms, including greedy algorithms, dynamic programming, linear and semi-definite programming, and randomization.
This course does not require specific prerequisite, other than basic knowledge in algorithms and in data structures.
Time & Date
Tuesdays, 10:00-12:00, HS003, E1 3
Thursdays 10:00–12:00 Room 016, E1 3
First lecture: Tuesday, April 25
- Dr. Tobias Mömke, Email: moemke at cs.uni-saarland.de
Office Hours: Whenever the door is open, E1 3, Room 422
- Dr. Hang Zhou, Email: hzhou at mpi-inf.mpg.de
Office Hours: Whenever the door is open, E1 4, Room 319
- Daniel Vaz, Email: ramosvaz at mpi-inf.mpg.de
Office Hours: Thursdays 14:00-16:00, E1 4, Room 314
PrerequesitesAlgorithms and Data Structures
Number of credit points: 6
|April 25, 2017||Introduction, TSP||Assignment 1 Script 1|
|May 2, 2017||TSP, Knapsack, Set Cover||Assignment 2 Script 2|
|May 9, 2017||Arora's Scheme||Assignment 3 Script 3|
|May 16, 2017||Linear Programming||Assignment 4 Script 4|
|May 23, 2017||Randomized Rounding||Assignment 5 Script 5|
|May 30, 2017||Prize-Collecting Steiner Tree||Assignment 6 Script 6|
|June 6, 2017||Uncapacitated Facility Location||Assignment 7 Script 7|
|June 13, 2017||Multicut, Region Growing Technique||Assignment 8 Script 8|
|June 20, 2017||Moat growing, Steiner Forests||Assignment 9 Script 9|
|June 27, 2017|
|July 4, 2017|
|July 11, 2017|
|July 18, 2017|
|July 25, 2017|
- David P. Williamson and David B. Shmoys, The Design of Approximation Algorithms, Cambridge University Press.
- Vijay V. Vazirani, Approximation Algorithms, Springer.