Approximation Algorithms
Dr. Tobias Mömke
Dr. Hang Zhou
News
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:Topic
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
Exercise Class:
Thursdays 10:00–12:00 Room 016, E1 3
First lecture: Tuesday, April 25
Lecturer
- 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
Assistants
- Daniel Vaz, Email: ramosvaz at mpi-inf.mpg.de
Office Hours: Thursdays 14:00-16:00, E1 4, Room 314
Prerequesites
Algorithms and Data StructuresGrading
Number of credit points: 6
Schedule
Date | Topic | Material |
---|---|---|
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 | Bootstrap problem | Assignment 10 Script 10 |
July 4, 2017 | Iterated Linear Programming - Introduction | Assignment 11 Script 11 |
July 11, 2017 | Iterated Linear Programming - Degree bounded MST | Assignment 12 Script 12 |
July 18, 2017 | Semidefinite Programming, Max Cut | Assignment 13 Script 13 |
July 25, 2017 | SDP: Vertex Coloring | Script 14 |
Literature
- David P. Williamson and David B. Shmoys, The Design of Approximation Algorithms, Cambridge University Press.
- Vijay V. Vazirani, Approximation Algorithms, Springer.