max planck institut
informatik
informatik
| Lectures: | Tuesday 14:15-16:00, room 024 (ground floor of the MPI-INF building E1.4) |
|---|---|
| Lecturers: | Anna Adamaszek and Andreas Wiese |
| Tutorials: | Thursday 14:15-16:00, every second week, room 024 (ground floor of the MPI-INF building E1.4) |
| Tutors: | Marvin Künnemann |
| Exam dates: | July 22, 14:00, room 309a in the MPI-INF building |
The re-exam takes place on Tuesday, September 16th. If you have any questions regarding the re-exam please send a mail to Andy.
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. Algorithms which find efficiently sub-optimal solutions, and give a guarantee on the quality of the solution for any input instance, are called approximation algorithms.
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. We will also focus on hardness of approximation, i.e., showing that getting good approximation algorithms for many optimization problems is NP-hard, i.e., as hard as finding an optimal solution for them.
Important: This is not a continuation of the class of the approximation algorithms class in WS 2013/04, but we will cover completely different topics. No previous knowledge of approximation algorithms is required. On the other hand, if you attended that class (and took the exam) you can still take this class (and take the exam).
| Prerequisites: | An undergraduate course in algorithms is a must. Additionally, some basic familiarity with programming (in any reasonable language) would be welcome. |
|---|---|
| Date | Topics | Lecture notes |
|---|---|---|
| Apr 15 | Introduction, minimum vertex cover, bin packing | Vazirani 1.1, LP-rounding for vertex cover (section 1), bin packing (10.1,10.2) |
| Apr 22 | Knapsack, set cover | Vazirani, Chapters 8.1, 8.2, and 2.1 |
| Apr 29 | TSP, metric TSP, max TSP, max asymmetric TSP | Vazirani, Chapter 3.2 |
| May 6 | Shortest superstring problem | Vazirani, Chapter 7 |
| May 13 | Makespan minimization on identical machines: List-Scheduling, Longest Processing Time (LPT) rule, PTAS |
Vazirani, Chapter 10, Hochbaum, Chapter 1 |
| May 20 | Makespan minimization on identical machines: PTAS (ct'd), List scheduling with release dates and precedence constraints: 2-approximation and hardness of approximation |
Vazirani, Chapter 10, Hochbaum, Chapter 1 |
| May 27 | Makespan minimization on unrelated machines: 2-approximation algorithm, 3/2-inapproximability result | Vazirani, Chapter 17, Paper "Graph balancing: a special case of scheduling unrelated parallel machines" |
| June 3 | Independent Set in Unit Disk Graphs: Greedy algorithm and PTAS, Independent Set of Rectangles: log(n)-approximation algorithm | Papers Marathe et al.: Simple Heuristics for Unit Disk Graphs, Hunt III et al.: NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs, and Berman et al.: Improved Approximation Algorithms for Rectangle Tiling and Packing |
| June 10 | Arora's PTAS for Euclidean TSP | Vazirani, Chapter 11 |
| June 17 | PTAS for Independent Set in planar graphs, graphs with bounded tree-width and exact algorithm for independent set in those graphs | Shmoys-Williamson, Chapter 10.2 |
| June 24 | Iterative rounding: rank lemma, matchings in bipartite graphs | Iterative Methods in Combinatorial Optimization: Chapter 2.1.1 and 3.1 |
| July 1 | Iterative rounding: generalized assignment problem, survivable network design (covered partially) | Iterative Methods in Combinatorial Optimization: Chapter 3.2 and 10.1 |
| July 8 | Hardness of approximation: introduction, PCP theorem, APX-hardness of MAX-3SAT and MAX-3SAT(3) | Vazirani, Chapter 29.1 -- 29.4 |
| July 15 | Hardness of approximation: minimum vertex cover, maximum clique | Vazirani, Chapter 29.5 -- 29.6 |
| July 22 | Exam |
| Date | Sheet | Topics |
|---|---|---|
| Apr 24 | Exercise Sheet 1 | Vertex Cover, Bin Packing, Knapsack |
| May 8 | Exercise Sheet 2 | Knapsack (ct'd), TSP, Shortest Superstring |
| May 22 | Exercise Sheet 3 | Scheduling |
| June 5 | Exercise Sheet 4 | Scheduling (ct'd), IS in geometric graphs |
| June 26 | Exercise Sheet 5 | Arora's PTAS, Treewidth |
| July 3 | Exercise Sheet 6 | Iterative Rounding |