TU Berlin

FG Kombinatorische Optimierung und GraphenalgorithmenApproximation Algorithms

COGA 5-Wheel

Inhalt

zur Navigation

Es gibt keine deutsche Übersetzung dieser Webseite.

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

Schedule

Weekday
Hour
Room
Lecture
Wednesday
10:15-11:45
MA 313
Lecture
Friday
10:15-11:45
MA 313

Slides and Lecture Notes

Sorted by chapter:

Sorted by date:

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

Homework

  1. 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.
  2. 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.
  3. 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:

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

Navigation

Direktzugang

Schnellnavigation zur Seite über Nummerneingabe