Approximation Algorithms

Course in Summer 2017

A large number of problems arising in practical scenarios like communication, transportation, planning, logistics etc. can be modeled as combinatorial optimization problems. In most cases, these problems are computationally intractable and one often resorts to heuristics that provide sufficiently good solutions in reasonable amount of runtime. However, in most cases, such heuristics do not provide a worst case guarantee on the performance in comparison to the optimum solution. In this course, we shall study algorithms for combinatorial optimization problems which can provide strong mathematical guarantees on performance. The course aims at developing a toolkit for solving such problems.  The lectures will consist of designing polynomial time algorithms and proving bounds on their worst case performances.

Instructors: Prof. Dr. Nicole Megow (Email)
Dr. Syamantak Das (Email)
Time & room: Wed 12-2 in room MZH 1090 (kurse)
Thu 10-12 in room MZH 5210 (kurse)

Start: Wednesday, April 5th, 2017

Resources: [1] The Design of Approximation Algorithms, David P. Williamson and David B. Shmoys
online version

[2] Approximation Algorithms, Vijay V. Vazirani
online version
Date Topic Notes Exercises
5.4.2017 Introduction, MST heuristic for TSP slides,Sections 1.1 and 2.4 from Williamson/Shmoys -
6.4.2017 Christofides' Algorithm, Makespan Greedy Sections 2.3 and 2.4 from Williamson/Shmoys Exercise 1
12.4.2017 Greedy Set Cover notes -
13.4.2017 Local Search: Max leaf spanning tree Lecture notes from R.Ravi's lectures at CMU -
19.4.2017 Local Search: k-median - -
20.4.2017 Local Search: k-median, Exercises Section 2.1 and 2.2 from this paper Exercise 2
26.4.2017 Introduction to LPs/ILPs, basic rounding (Vertex Cover) - -
27.4.2017 ILP for Spanning Trees, Cut-Lps, Separation Oracles, Prize Collecting Vertex Cover - Exercise 3
03.5.2017 LP Rounding : Weighted Sum of Completion Time on Single and Parallel Machines - -
04.5.2017 Exercises - -
10.5.2017 Shmoys, Tardos rounding for Minimizing Makespan Section 11.1 from [1] -
11.5.2017 Introdution to primal-dual, vertex cover - Exercise 4
17.5.2017 Steiner Forest using primal-dual Section 7.4 of [1] -
18.5.2017 No lecture - -
24.5.2017 PTAS: Bin-packing, Makespan Sections 3.2,3.3 of [1] -
25.5.2017 No Lectures - Exercise 5
31.5.2017 FPTAS, Knapsack Section 3.1 of [1] -
31.5.2017 Exercises Exercise 6