ADM III: Approximationsalgorithmen - SS 2008

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. Der Schwerpunkt liegt dabei klar auf Techniken, die auf linearer Programmierung beruhen. Es sollen folgende Themen behandelt werden:

• (Nicht-)Approximierbarkeit
• LP-Runden: randomisiert, deterministisch, iteriert, ...
• Dual Fitting, Primal-duales Schema, Local Ratio Methode
• Schranken aus semidefiniten Relaxationen
• Polynomiale Approximationsschemata, MAX-SNP-hardness, PCP Theorem
• metrische Einbettungen
• Sample und Augment
• ...

Die Veranstaltung ist als 3. Teil des Zyklus Algorithmische Diskrete Mathematik (ADM III) zulässig.
Bachelor-Studierende finden diesen Kurs als "vertiefende Veranstaltung".

Aktuelles

Die Vorlesung und Übungen finden als Blockveranstaltung am Ende des Semesters statt. TERMIN 29.9.-10.10. in Raum MA043. Das Wochenende, sowie der 3.10. bleiben frei, ansonsten ganztags (d.h. ca 9.15-17.00 mit Mittagspause). Alle Aufgaben bearbeiten wir während des Tages, also keine extra Hausaufgaben. Es gibt auch keine Programmieraufgaben (endlich mal!).

Termine

Blockvorlesung zum Ende des Semesters, s. Aktuelles.

Kontakt

Literatur/Skript

Parallel zu den Vorlesungen im SS04 und WS2006/7 habe ich ein Skript ausgearbeitet (das nicht 100% fehlerfrei ist...): PDF
Dieses Skript wird im Laufe der Vorlesung korrigiert, aktualisiert und erweitert. Einiges Material wird vermutlich entrümpelt...

Die Literaturliste...

Verschiedene Bücher zu einzelnen (auch nur am Rande berührten) Themen und Problemen der Vorlesung können bei mir (MA 502) 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.
  

• Klaus Jansen und Marian Margraf, Approximative Algorithmen und Nichtapproximierbarkeit, de Gruyter, Berlin, 2008.

Weiterhin interessant:

• 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
• Reuven Bar-Yehuda, Dror Rawitz: A Tale of Two Methods. Lecture Notes in Computer Science 3895, S.196-217, 2006.

Noch mehr Skripte

• Michel Goemans, Skript zur Vorlesung, MIT, 1994.
• Rajeev Motwani, Skript zur Vorlesung, Stanford, 1991
• David Williamson, Skript zur Vorlesung, Cornell, 1998

Scheinkriterien

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