### Page Content

### to Navigation

# Approximation Algorithms (ADM III)

An approximation algorithm for an NP-hard optimization problem is a polynomial time algorithm that always finds a feasible solution whose value is provably close to the optimum solution value. More precisely, the value of the computed solution must be within a factor alpha of the optimum. alpha is the performance guarantee of the approximation algorithm.

The field of approximation algorithms is among the most active research areas of algorithmic discrete mathematics today. It combines a rich and deep mathematical theory with the promise of profound practical impact.

In order to follow the course, profound knowledge of linear and combinatorial optimization is required.

## News

- The
**oral exams**take place on**March 6th**and**March 25th**, 2013. Please sign up for a date and time slot at the secretary's office MA 501. - The
**preparatory meeting**of next semester's**seminar on Approximation Algorithms**will take place on**February 13**, 2013 after class (at 11:45 h). - There is
**no class**on the following days:**Feb. 6, Feb. 8**.

## Contact Information

The classes are given by Martin Skutella.

Office hours: Tuesday 11-12 h

## Slides and Lecture Notes

**Sorted by chapter:**

- Preliminaries
- Chapter 1: An Introduction to Approximation Algorithms
- Chapter 2: Greedy Algorithms and Local Search
- Chapter 3: Rounding Data and Dynamic Programming
- Chapter 4: Deterministic Rounding of Linear Programs
- Chapter 5: Random Sampling and Randomized Rounding of LPs
- Chapter 6: Randomized Rounding of Semidefinite Programs
- Chapter 7: The Primal-Dual Method
- Chapter 8: Cuts and Metrics
- Chapter 9: Hardness of Approximation

**Sorted by date:**

- Lecture 17/10/2012: slides (Introduction, Set Cover: LP-based deterministic rounding, dual rounding)
- Lecture 24/10/2012: slides (Set Cover: primal-dual, greedy, nonapproximability; scheduling with due dates on a single machine)
- Lecture 26/10/2012: slides (scheduling with due dates on a single machine,
*k*-Center Problem, scheduling on identical parallel machines) - Lecture 31/10/2012: slides (list scheduling on identical parallel machines and LPT rule, insertion heuristic for TSP, Minimum-Degree Spanning Trees)
- Lecture 01/11/2012: Discussion of solutions to Exercises 1.3, 1.5, 2.1, and 2.3 from the Williamson-Shmoys book.
- Lecture 07/11/2012: slides (FPTAS for Knapsack Problem, PTAS for scheduling on identical parallel machines)
- Lecture 09/11/2012: slides (existence of FPTASes, asymptotic PTAS for Bin-Packing)
- Lecture 14/11/2012: slides (single machine scheduling with total weighted completion time objective)
- Lecture 16/11/2012: slides (Steiner Tree Problem; Prize-Collecting Steiner Tree Problem)
- Lecture 21/11/2012: slides (Uncapacitated Facility Location Problem; Bin Packing revisited)
- Lecture 22/11/2012: Discussion of solutions to Exercises 2.13, 3.3, 4.1, and 4.3 from the Williamson-Shmoys book.
- Lecture 23/11/2012: slides (Bin Packing with OPT+O(log
^{2}OPT) bins) - Lecture 28/11/2012: slides (Randomized approximation algorithms, MAX SAT, MAX CUT)
- Lecture 29/11/2012: slides (MAX SAT: Derandomization by mathod of conditional expectations, flipping biased coins, randomized rounding, choosing better of two solutions)
- Lecture 30/11/2012: slides (non-linear randomized rounding, randomized approximations for Prize-Collecting Steiner Trees and Uncapacitated Facility Location)
- Lecture 05/12/2012: slides (randomized rounding: minimizing weighted sum of completion times, minimum capacity multicommodity flow)
- Lecture 07/12/2012: slides (coloring dense 3-colorable graphs, semidefinite programs and vector programs)
- Lecture 12/12/2012: slides (SDP-based approximation of MAX CUT and 3-Coloring)
- Lecture 13/12/2012: Discussion of solutions to Exercises 4.4, 4.7, 5.2, and 5.8 from the Williamson-Shmoys book.
- Lecture 14/12/2012: slides (Prima-dual algorithms for Set Cover, Feedback Vertex Set, Shortest
*s-t*-path) - Lecture 21/12/2012: slides (Primal-dul algorithm for Steiner Forest Problem)
- Lecture 16/01/2013: slides (Primal-dul algorithm for Minimum Knapsack Problem and Uncapacitated Facility Location Problem)
- Lecture 18/01/2013: slides (Primal-dul algorithm for
*k*-Median Problem) - Lecture 23/01/2013: guest lecture by Nicole Megow on universal sequencing
- Lecture 30/01/2013: slides (Multiway Cut Problem)
- Lecture 01/02/2013: slides (Multicut Problem)
- Lecture 13/02/2013: slides (Inapproximability of MaxClique, PCP Theorem)
- Lecture 15/02/2013: slides (L-Reductions, Inapproximability of MAX2SAT)

## Homework

- 26/10/2012: Solve Exercises 1.3, 1.5, 2.1, and 2.3 from the Williamson-Shmoys book. The solutions will be discussed in class on November 1.
- 14/11/2012: Solve Exercises 2.13, 3.3, 4.1, and 4.3 from the Williamson-Shmoys book. The solutions will be discussed in class on November 22.
- 06/12/2012: Solve Exercises 4.4, 4.7, 5.2, and 5.8 from the Williamson-Shmoys book. The solutions will be discussed in class on December 13.

## Literature

The course is based on selected chapters of the following book:

- David P. Williamson, David B. Shmoys,
*The Design of Approximation Algorithms*, Cambridge University Press, 2011

Further reading:

- G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela, M. Protasi,
*Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties*, Springer Verlag, 1999 - D. S. Hochbaum (ed.), Approximation Algorithms for NP-Hard Problems, PWS Publishing Company, 1995
- B. Korte, J. Vygen, Combinatorial Optimization, Springer Verlag, 5th edition, 2012
- V. V. Vazirani,
*Approximation Algorithms*, Springer Verlag, 2001