ADM III: Approximationsalgorithmen - WS 2006/07

Inhalt

Für NP-schwere Optimierungsprobleme können wir nicht erwarten, effiziente Algorithmen zu finden, es sei denn, P=NP. Verzichtet man hingegen auf Optimalität und fordert von einem Algorithmus, dass er "nur" eine beweisbar gute Qualität, diese dafür aber in polynomialer Laufzeit liefert, so sprechen wir von Approximationsalgorithmen.

Anhand von Beispielen vor allen aus der kombinatorischen Optimierung wollen wir einige algorithmische Ideen und Werkzeuge dieses innerhalb der diskreten Mathematik und theoretischen Informatik sehr aktuellen und lebendigen Themas verdeutlichen. Ein Schwerpunkt liegt dabei auf Techniken, die auf linearer Programmierung beruhen. Die momentane Planung (Sommer 2006) sieht vor, folgende Themen zu behandeln:

• Polynomiale Lösbarkeit und NP-Vollständigkeit
• LP-Runden: randomisiert, deterministisch, iteriert, ...
• Dual Fitting, Primal-duales Schema, Local Ratio Methode
• Schranken aus semidefiniten Relaxationen
• Polynomiale Approximationsschemata, MAX-SNP-hardness
• ...

Die Veranstaltung ist als 3. Teil des Zyklus Algorithmische Diskrete Mathematik (ADM III) zulässig.

Aktuelles

20.12.: Die erste Vorlesung im neuen Jahr ist am 16.01.2007.

22.11.: Der Dienstagstermin ist ab sofort um 8.30.

19.10.: Es gibt neue Vorlesungstermine; für beide Termine haben wir den Raum MA 548.

Entgegen *aller* anderen Ankündigen beginnt die Vorlesung regulär in der ersten Semesterwoche, d.h. am 18.10.!

Termine

Die Vorlesung ist eine sogenannte integrierte Veranstaltung, d.h. wir werden etwa ein Viertel der Zeit mit Übungen verbringen, ohne dass wir dabei einem strikten Zeitplan folgen müssen.

Kontakt

Literatur/Skript

Parallel zur Vorlesung im SS2004 habe ich ein Skript ausgearbeitet (das noch nicht 100% fehlerfrei ist...): PDF
Dieses Skript wird im Laufe der Vorlesung korrigiert, aktualisiert und erweitert, hier ist die aktuelle Version vom 15.2.2007: PDF

Der Abschnitt über k-Median fehlt noch immer. Bis dahin das Paper von Jain und Vazirani...

Die Literaturliste...

Verschiedene Bücher zu einzelnen (auch nur am Rande berührten) Themen und Problemen der Vorlesung können bei mir (MA 610) eingesehen/ausgeliehen werden. Dies trifft insbesondere auf lineare, ganzzahlige und kombinatorische Optimierung zu.

Die beiden Bücher über Approximationsalgorithmen

• Dorit S. Hochbaum (Hrs.), Approximation Algorithms for NP-Hard Problems, PWS Publishing Company, Boston, MA, 1996.
  
  • Informationen zum Buch
  • Bestellinfo
• Vijay V. Vazirani, Approximation Algorithms, Springer, Berlin, 2001.
  

• G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela und M. Protasi, Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties, Springer, Berlin, 1999. siehe hierzu auch online:
• Pierluigi Crescenzi und Viggo Kann, A Compendium of NP Optimization Problems

Komplexitätstheorie

• Michael R. Garey und David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman and Company, New York, 1979.
• Ingo Wegener, Complexity Theory: Eploring the Limits of Efficient Algorithms, Springer, Berlin, 2005.
• Christos H. Papadimitriou, Computational Complexity, Addison Wesley, 1993.

Weiterführende Zeitschriftenartikel zu speziellen Themen

• Michel X. Goemans und David P. Williamson, Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming, Journal of the ACM, 42, 1115-1145, 1995.
• Dorit S. Hochbaum, Instant recognition of half-integrality and 2-approximation, Proceedings of APPROX98, Aalborg, Denmark, 1998.
• Kamal Jain, A Factor 2 Approximation Algorithm for the Generalized Steiner Network Problem, Combinatorica, 21, 39-60, 2001.
• Joe S.B. Mitchell, Guillotine Subdivisions Approximate Polygonal Subdivisions: A simple polynomial-time approximation scheme for geometric TSP, k-MST, and related problems, SIAM J. Computing, 28(4), 1298-1309, 1999.
• Michel X. Goemans und David P. Williamson, New 3/4-Approximation Algorithms for the Maximum Satisfiability Problem, SIAM Journal on Discrete Mathematics, 7, 656-666, 1994.
• Sanjeev Arora und Carsten Lund, Hardness of Approximations. In Approximation Algorithms for NP-hard Problems, Dorit Hochbaum (Hrs.), PWS Publishing, 1996.
• Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan und Mario Szegedy, Proof Verification and Hardness of Approximation Problems. Journal of ACM, 45(3):501-555, 1998.
• Sanjeev Arora and Muli Safra, Probabilistic Checking of Proofs: A New Characterization of NP. Journal of ACM, 45(1):70-122, 1998.
• David B. Shmoys, Chaitanya Swamy, Retsef Levi: Facility location with Service Installation Costs. Proceedings of SODA 2004, S.1088-1097

Noch mehr Skripte

• Das Skript von Michel Goemans ist nach zehn Jahren noch immer "erfrischend", MIT, 1994.
• Rajeev Motwani, Skript zur Vorlesung, Stanford, 1991
• David Williamson, Skript zur Vorlesung, Cornell, 1998

Übungsblätter

Die Bearbeitungszeit beträgt in der Regel eine Woche. Ich gebe Kommentare zu allen Lösungen der Übungsaufgaben, die mir abgegeben werden. Wir werden die Aufgaben in jedem Fall in der Vorlesung/Übung gemeinsam diskutieren.

• Übung 1 vom 01.11.2006: PDF
• Übung 2 vom 15.11.2006: PDF
• Übung 3 vom 29.11.2006: PDF
• Übung 4 vom 21.12.2006: PDF
• Übung 5 vom 31.01.2006: PDF (Unixpool)

Scheinkriterien

Aktive Teilnahme an der Lösung der Übungsaufgaben; Rücksprache am Ende des Semesters.