 max planck institut
informatik # Approximation Algorithms and Hardness of Approximation

## Basic Information

Lectures: Tuesday 14:15-16:00, room 024 (ground floor of the MPI-INF building E1.4) Anna Adamaszek and Andreas Wiese Thursday 14:15-16:00, every second week, room 024 (ground floor of the MPI-INF building E1.4) Marvin Künnemann 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.

### Description

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.

### Lectures

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

### Exercises

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

### Textbooks used in this course

• "Approximation Algorithms" by V. Vazirani (pdf)
• "Approximation Algorithms for NP-Hard Problems" by Dort S. Hochbaum (editor) (info)

More Courses of the Algorithms and Complexity Group

Search MPII (type ? for help)