Approximation Algorithms (SS 2012)

Description, Time Schedule, Location: kvv

News: Presentation dates: 19, 20 July.
Room: 055

*** Program ***

19 July:

10:00--11:00 P. Seiferth, 'An approximation algorithm for maximum independent set in planar graphs based on planar separators'
11:00--12:00 T. Rakowski, 'An (OPT+1)-apx algorithm for the minimum degree spanning tree problem'
14:00--15:00 P. Podlech, 'Hardness of approximation: reductions from label cover'
15:00--16:00 Y. Stein, 'Unique games'
_______

20 July:

10:00--11:00 R.L. Gottwald, 'A primal-dual-algorithm for the prize-collecting Steiner tree problem'
11:00--12:00 M. Wisniewski, 'Probabilistic approximation of metrics by tree metrics'
14:00--15:00 J. Meier, 'Survivable network design and iterated rounding'
15:00--16:00 M. Konzack, M. Meekes, 'The single-source rent-or-buy problem and the Steiner tree problem'


Lectures:
  1. Basics ([1]: pp 3-6. [2]: pp 1-2, 346-348. [4]: pp xiii-xvii).
    Vertex cover ([2]: pp 1-5).
  2. Set Cover ([1]: 1.6. [2]: pp 15-17).
    TSP ([1]: 2.4. [2]: 3.2).
  3. TSP (cont.).
    Scheduling ([1]: 2.1, 2.3. [2]: 10.1).
  4. Scheduling (cont.).
  5. (Tutorial) MAX-CUT (Local search, random sampling [1]: 5.1).
  6. Knapsack ([1]: 3.1. [2]: 8).
  7. Minimum-degree spanning tree ([1]: 2.6).
  8. LP techniques: Set Cover (deterministic rounding, [1]: 1.2, 1.3. [6]: 3.1, 3.3, 3.4).
  9. (Tutorial) LP (Primal-Dual formulations, strong-weak duality, compl. slackness).
  10. Uncapacitated Facility Location (Deterministic rounding via dual, [1]: 4.5).
  11. Primal-Dual method (Set Cover, [1]: 1.4, 1.5, 7.1. [2]: 15.1, 15.2).
  12. (Tutorial) Primal-Dual for min s-t path ([1]: 7.3).
  13. Feedback Vertex Set (PD, [1]: 7.2).
  14. (Tutorial) Generalized Steiner Tree (PD, [1]: 7.4).
  15. Generalized Steiner Tree (cont.).
  16. (29.06) Randomized LP rounding ([1]: 1.7).
  17. (05.07) MAX-SAT (Everything you should/wanted to know).
  18. Semidefinite Programming ([1]: 6.1, 6.2. [2]: 1, 2.).
  19. SDP (cont.), Innaproximability.
  20. Inapproximability (cont.).
Exercises:
Ex.1.
Ex.2 (corrected typo).
Ex.3. (A solution to Ex.3.1 can be found in: C. Bazgan, M. Santha, and Z. Tuza, 'Efficient approximation algorithms for the subset-sums equality problem', JCSS, 2002.)
Ex.4.
Ex.5 (Reading Assignment): Study the chapters cited above for the Primal-Dual method (Lecture 11).
Ex.6.

Literature:

[1] The Design of Approximation Algorithms, D.P. Williamson and D.D. Smoys, Cambridge University Press, 2011.
[2] Approximation Algorithms, V.V. Vazirani, Springer, 2001.
[3] Geometric Approximation Algorithms, S. Har-Peled, AMS, 2011.
[4] Approximation Algorithms for NP-hard Problems, D. Hochbaum (Eds.), 1996.
[5] Approximationsalgorithmen Eine Einführung, Rolf Wanka, Teubner, 2006.
[6] Understanding and Using Linear Programming, J. Matoušek and B. Gärtner, Springer 2006.
[7] Approximation Algorithms and Semidefinite Programming, B. Gärtner and J. Matoušek, Springer 2012.