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.
- 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.
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(log2OPT) 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)
- 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.
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
- 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