Dr. Tobias Mömke
Dr. Hang Zhou
NewsPlease register for the course.
We have the option to change the time of the exercise class. Please enter the time slots that fit for you into the Doodle poll accessible with the link below. On Thursday, April 27, the exercise class will take place from 10-12 as announced.
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: -, 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|
|May 9, 2017|
|May 16, 2017|
|May 23, 2017|
|May 30, 2017|
|June 6, 2017|
|June 13, 2017|
|June 20, 2017|
|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.