Saarland University
Department of Computer Science
Computational Complexity
Computational Complexity

Publications

Teaching

Workshops

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:

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

Lecture:
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

Assistants

Prerequesites

Algorithms and Data Structures

Grading

50% of scores from exercises are required to participate at the exam.

Number of credit points: 6

Schedule

DateTopicMaterial
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