Approximationsalgorithmen - SS 2004

Dozent: Marco Lübbecke
Nummer der LV: 0230 L 254

Für viele Entscheidungs- bzw. Optimierungsprobleme kann man beweisen, dass ein effizienter Algorithmus nicht existieren kann. Den Hintergrund für diese Art von Aussagen bildet die Komplexitätstheorie, mit der wir uns eingangs beschäftigen. 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 u.a. 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 (Februar 2004) 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
• ...

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

Termine

siehe auch "Aktuelles"

Aktuelles

Die Seminarvorbesprechung findet am 15.7. um 16.00 im MA606 statt.

Die ausgefallenen Stunden holen wir am Freitag, 23. Juli 2004, 10.00-16.00 "im Block" nach; Ort: Café Möhring = MA606. Wir wollen versuchen, den folgenden Artikel gemeinsam zu verstehen:

• David B. Shmoys, Chaitanya Swamy, Retsef Levi: Facility location with Service Installation Costs. Proceedings of SODA 2004, S.1088-1097

Im Wintersemester 2004/2005 bietet unsere Arbeitsgruppe ein Seminar Scheduling und Approximationsalgorithmen an.

Anlässlich des 125-jährigen Jubiläums der TU Berlin findet am 5.5.04 eine Festveranstaltung im H104 von 9-12 statt. Unsere Vorlesung fällt an diesem Tag mit der Bitte um Teilnahme an der Festveranstaltung aus.

Der Dienstagstermin findet nun von 12-14 statt, nach wie vor im MA645!
Die erste Vorlesung findet am 13. April 2004 statt.

Anfang Juni 2004 wird die Vorlesung für etwa zwei Wochen ruhen. Wir werden am Anfang des Semesters hierfür gemeinsam Ausweichtermine festlegen, die an dieser Stelle gepostet werden.

Kontakt

Literatur

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

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

• Übung 1 vom 20. April 2004: ps.gz, PDF
  Aktualisiert am 3. Mai nach den Kommentaren in der Übung.
  Siehe das O(log n)-Bespiel für Vertex Cover z.B. hier.
• Übung 2 vom 4. Mai 2004: ps.gz, PDF
  Minimum Multicut (Aufgabe 3) wird am 11.5. definiert.
• Übung 3 vom 19. Mai 2004: ps.gz, PDF
• Übung 4 vom 28. Juni 2004: ps.gz, PDF
• Übung 5 vom 2. Juli 2004: ps.gz, PDF

Scheinkriterien

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

source last modified: Tue Jul 20 2004, last built: Tue Jul 20 2004 Marco Lübbecke <m.luebbecke@math.TU-Berlin.DE>