Approximation Algorithms (MA5517)

An approximation algorithm for an optimization problem is an algorithm that runs in polynomial time in the size of the input and computes a solution that is guaranteed to be within a certain factor of the optimal solution. This course will cover general techniques for designing approximation algorithms such as greedy algorithms, LP rounding, and the primal-dual method. We will apply these techniques to derive algorithms for many fundamental combinatorial optimization problems such as the Steiner tree problem, the traveling salesman problem, or the set cover problem.

Basic Information

Weekly Hours: 2+1 (4+2 over 7 weeks) / 5 ECTS

News

• Registration for 2nd round of exams via TUM online from January 1-15, 2019.
• The course is over. Thank you for your participation!

Schedule

The course will be going on over 7 weeks from October 22 to December 7.

Lectures

Tutorials

Slides/Lecture Notes

• Lecture 1 (Oct 22, 2018): Introduction to Approximation Algorithms; Set Cover Problem: LP Rounding, Primal-dual Method, Greedy Algorithm. Suggested Reading: Chapter 1 of The Design of Approximation Algorithms. (slides) (notes)
• Lecture 2 (Oct 24, 2018): Set Cover Problem: Randomized LP Rounding, Hardness of Approximation; Combinatorial Lower Bounds for the Traveling Salesman Problem. Suggested Reading: Sections 1.7 & 2.4 of The Design of Approximation Algorithms. (slides) (notes)
• Lecture 3 (Oct 29, 2018): Greedy Algorithms and Local Search: Minimum Spanning Trees, Scheduling on Identical Parallel Machines, k-Center Problem. Suggested Reading: Sections 2.2 & 2.3 of The Design of Approximation Algorithms. (slides) (notes)
• Lecture 4 (Nov 5, 2018): Dynamic Programming and Rounding the Input Data: Knapsack. Suggested Reading: Sections 3.1 & 3.2 of The Design of Approximation Algorithms. (slides) (notes)
• Lecture 5 (Nov 7, 2018): Dynamic Programming and Rounding the Input Data (continued): Scheduling on Identical Parallel Machines. Suggested Reading: Sections 3.1 & 3.2 of The Design of Approximation Algorithms. (slides) (notes)
• Lecture 6 (Nov 12, 2018): LP Rounding: Prize-collecting Steiner Tree and Uncapacitated Facility Location. Suggested Reading: Sections 4.3-4.5 & 5.7-5.8 of The Design of Approximation Algorithms. (slides) (notes)
• Lecture 7 (Nov 14, 2018): Random Sampling and Randomized LP Rounding: Uncapacitated Facility Location (continued), Maximum Satisfiability. Suggested Reading: Sections 5.1-5.6 & 5.8 of The Design of Approximation Algorithms. (slides) (notes)
• Lecture 8 (Nov 19, 2018): LP Rounding for Max Sat; Chernoff Bounds: Integer Multicommodity Flows; Rounding Semidefinite Programs: MAX CUT. Suggested Reading: Sections 5.9-5.10 & Chapter 6 of The Design of Approximation Algorithms. (slides) (notes)
• Lecture 9 (Nov 21, 2018): The Primal-Dual Method: The Generalized Steiner Tree Problem. Suggested Reading: Sections 7.1-7.4 of The Design of Approximation Algorithms. (slides) (notes)
• Lecture 10 (Nov 26, 2018): Primal-dual Method for Uncapacitated Facility Location; Lagrangean Relaxation for the k-Median Problem. Suggested Reading: Sections 7.6 & 7.7 of The Design of Approximation Algorithms. (slides) (notes)
• Lecture 11 (Nov 28, 2018): Lagrangean Relaxation for the k-Median Problem (continued); Iterated Rounding for Survivable Network Design. Suggested Reading: Section 11.3 of The Design of Approximation Algorithms. (slides) (notes)
• Lecture 12 (Dec 3, 2018): Iterated Rounding for Survivable Network Design (continued). Suggested Reading: Section 11.3 of The Design of Approximation Algorithms. (slides) (notes)
• Lecture 13 (Dec 5, 2018): Randomized Iterated Rounding for Steiner Tree; SDP Rounding for Max Cut. Suggested Reading: Sections 12.3 and 6.2 of The Design of Approximation Algorithms. (slides) (notes)
• FAQ Session (Dec 12, 2018)

Problem Sets

• Problem Set 1 Answers
  Applying Results on the Approximability of the Set Cover Problem
  (discussed on October 30th/31th, 2018)
• Problem Set 2 Answers
  Greedy Algorithms and Combinatorial Bounds
  (discussed on November 6th/7th, 2018)
• Problem Set 3 Answers
  Relaxed Decision Procedures and a FPTAS
  (discussed on November 13th/14th, 2018)
• Problem Set 4 Answers
  Linear Programming Relaxations and Rounding
  (discussed on November 20th/21th, 2018) 
• Problem Set 5 Answers
  Derandomization and the Primal-Dual Method
  (discussed on November 27th/28th, 2018)
• Problem Set 6 Answers
  The Primal-Dual Method and Iterated Rounding
  (discussed on December 4th/5th, 2018)

Literature

The course will be based on the 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
• M. Mitzenmacher, E. Upfal, Probability and Computing: Randomized Algorithms and Probabilistic Analysis, Cambridge University Press, 2005
• V. V. Vazirani, Approximation Algorithms, Springer Verlag, 2001