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:

Williamson, Shmoys
Vazirani

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

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 Structures

Grading

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.