# 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. |

# 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. 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).

# Lectures

Date | Topics | Lecture notes |
---|---|---|

October 20 | Organization, introduction, Set cover: LP-rounding and greedy algorithm | Shmoys-Williamson Chapters 1.1, 1.2, 1.3, 1.6 |

October 27 | Greedy algorithms: NextFit and FirstFit Decreasing for Bin Packing, Greedy algorithm for Knapsack, List Scheduling for minimizing the makespan on identical machines | Lecture notes by Susanne Albers and Alexander Souza, Lecture notes by Chandra Chekuri (scribe: Kyle Fox), Shmoys-Williamson Chapter 2.3 |

November 3 | FPTAS for knapsack, asympotic PTAS for bin packing | Vazirani Chapters 8 and 9 |

November 10 | 2-approximation for minimizing the makespan on unrelated machines, (3/2-eps)-inapproximability result | Vazirani 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 24 | Art Gallery problem (vertex-guarding), clustering problems. | Syllabus, Paper by S.K. Ghosh, Chapter 2 of Har-Peled's book. |

December 1 | Grids: Minimun distance pair, k-enclosing minimum disk, min enclosing disk. | Chapter 1 of Har-Peled's book. |

December 8 | Karmarkar Karp algorithm for bin packing | Shmoys-Williamson Chapter 4.6 |

December 15 | Local search algorithm for uncapacitated facility location | Shmoys-Williamson Chapter 9.1 |

January 5 | Voronoi diagrams | Chapter 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 12 | Duality and Delaunay Triangulations | Chapters 8 and 9 of CGAA. |

January 19 | Duality and Delaunay Triangulations ctd. | Chapters 8 and 9 of CGAA. |

January 26 | Linear programming in low dimensions | Chapter 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 9 | Johnson Lindenstrauss Lemma. Recap | Chapter 8 of Har-Peled's book. Elementary proof. |

# Exercises

Tutorial | Sheet | Due Date |
---|---|---|

29.10.2015 | Exercise Sheet 1 | 11.11.2015 |

11.11.2015 | Exercise Sheet 2 | 25.11.2015 |

25.11.2015 | Exercise Sheet 3 | 9.12.2015 |

9.12.2015 | Exercise Sheet 4 | 6.1.2016 |

6.1.2016 | Exercise Sheet 5 | 22.1.2016 |

22.1.2016 | Exercise Sheet 6 | 5.2.2016 |

# Literature

In this lecture we use material from the following textbooks

- "Approximation Algorithms" by V. Vazirani (pdf)
- "The Design of Approximation Algorithms" by David P. Williamson and David B. Shmoys (pdf)