Approximation Algorithms

Advanced Course, 2+1

Basic Information

Lectures:Tuesday 10:15-11:45, room 024 in the ground floor of the MPI-INF building E1.4
Lecturers:Mayank Goswami and Andreas Wiese
First lecture:Tuesday, October 20, 10:15am
Tutorials:Wednesday 14:15-16:45, every second week, room 024 in the ground floor of the MPI-INF building E1.4
Tutor:Andreas Schmid
First tutorial:Thursday, October 29, 10:15am
Credits:5 credit points
Prerequisites:An undergraduate course in algorithms is a must. Additionally, some basic familiarity with programming (in any reasonable language) would be welcome.


For many important optimization problems we cannot find an optimal solution efficiently. If we want to obtain a solution in a reasonable amount of time, we have to give up optimality and aim for getting a solution with a value as close as possible to the value of an optimal solution. This leads to approximation algorithms which are algorithms that run fast and still give a guarantee on the quality of the solution for any input instance.

The area of approximation algorithms is one of the core areas of modern theoretical computer science. We will discuss approximation algorithms for various classes of problems, including, but not limited to, scheduling, geometric problems and problems on planar graphs. You will learn many important paradigms in the design of approximation algorithms such as LP-rounding, local search, or greedy algorithms. We will also study hardness of approximation, i.e., how one can show that finding a good approximative solution for a problem is NP-hard (and thus as hard as finding the optimal solution).

No previous knowledge of approximation algorithms is required. Please note that you cannot take the exam of this class if you already took the exam of the approximation algorithms class in the summer semester 2014 or in the winter semester 2013/14 (since their contents overlap with this lecture).


DateTopicsLecture notes
October 20Organization, introduction, Set cover: LP-rounding and greedy algorithmShmoys-Williamson Chapters 1.1, 1.2, 1.3, 1.6
October 27Greedy algorithms: NextFit and FirstFit Decreasing for Bin Packing, Greedy algorithm for Knapsack, List Scheduling for minimizing the makespan on identical machinesLecture notes by Susanne Albers and Alexander Souza, Lecture notes by Chandra Chekuri (scribe: Kyle Fox), Shmoys-Williamson Chapter 2.3 
November 3FPTAS for knapsack, asympotic PTAS for bin packingVazirani Chapters 8 and 9
November 10 2-approximation for minimizing the makespan on unrelated machines, (3/2-eps)-inapproximability resultVazirani Chapter 17, the inapproximability result is from the paper "Graph balancing: a special case of scheduling unrelated parallel machines". A brief introduction on linear programming can be found in Appendix A of the Shmoys-Williamson textbook. 
November 17

PTAS for Maximum Independent Set in planar graphs, graphs with bounded tree-width and exact algorithm for independent set in those graphs.

Shmoys-Williamson Chapter Chapter 10.2. The claims not proven in the lecture are proven in Lemmas 10.13, 10.14, and 10.15 there.

November 24Art Gallery problem (vertex-guarding), clustering problems.SyllabusPaper by S.K. Ghosh, Chapter 2 of Har-Peled's book.
December 1Grids: Minimun distance pair, k-enclosing minimum disk, min enclosing disk. Chapter 1 of Har-Peled's book.                 
December 8Karmarkar Karp algorithm for bin packingShmoys-Williamson Chapter 4.6
December 15 Local search algorithm for uncapacitated facility locationShmoys-Williamson Chapter 9.1
January 5Voronoi diagramsChapter 7 of CGAA by De Berg et. al. Assigned reading: Chapter 2 on Sweep Line paradigm and Section 4.2 on half-plane intersection.
January 12Duality and Delaunay TriangulationsChapters 8 and 9 of CGAA.
January 19Duality and Delaunay Triangulations ctd.Chapters 8 and 9 of CGAA.
January 26Linear programming in low dimensionsChapter 4 of CGAA.
February 2 Duality 3SUM hardness of strips-cover-box, relation between voronoi, convex hulls, delaunay and half plane intersection.Chapter 11 of CGAA. 3SUMHARD-Geometric-problems.
February 9Johnson Lindenstrauss Lemma. RecapChapter 8 of Har-Peled's book. Elementary proof.


TutorialSheetDue Date
29.10.2015Exercise Sheet 1


11.11.2015Exercise Sheet 225.11.2015
25.11.2015Exercise Sheet 3


9.12.2015Exercise Sheet 4


6.1.2016Exercise Sheet 522.1.2016
22.1.2016Exercise Sheet 65.2.2016


In this lecture we use material from the following textbooks