Fakultät für Informatik der Technischen Universität München Lehrstuhl für Effiziente Algorithmen Postadresse: 80290 München; Hausadresse: Arcisstr.21, 80333 München

Hauptseminar Approximative Algorithmen

Angebotene Themen

Thema 1:

Komplexität von Optimierungsproblemen I

• Kurze Einführung in die Werkzeuge der Komplexitätstheorie: Komplexitätsklassen, Reduktionen, Vollständigkeit
• Definition von Optimierungsproblemen, PO- und NPO-Probleme, NP-harte Optimierungsprobleme [ACG,1.4]
• Maße der Approximationsqualität; Beispiel: 2-Approximation für MAXSAT [ACG,3.1]
• Die Klasse APX [ACG,3.1]
• Approximierbarkeit und Nichtapproximierbarkeit des TSP, Christofide's Algorithmus [ACG,3.1]
• Grenzen von APX: Die Gap-Technik [ACG,3.1]

Thema 2:

Komplexität von Optimierungsproblemen II

• Kurze Wiederholung: Klasse APX und ihre Grenzen [ACG,3.1]
• Die Klasse PTAS; Beispiele: Approximationsschemata für MIN PARTITION und für MAX INT KNAPSACK [ACG,3.2]
• APX versus PTAS, Zusammenhang mit P$\neq$NP [ACG,3.2]
• Die Klasse FPTAS [ACG,3.3]; Beispiel: fully poly-time Approximationsschema für MAX KNAPSACK [ACG,p.72]
• Probleme außerhalb von FPTAS: Polynomiell beschränkte Optimierungsprobleme [ACG,3.3]
• Psdeudopolynomielle und im strengen Sinne NP-harte NPO-Probleme [ACG,3.3]

Thema 3:

Komplexität von Optimierungsproblemen III

• Wiederholung: Klasse PTAS; Beispiel: Approximationssschema für MAX INDEPENDENT SET mit Beweis für exponentiellen
  Zusammenhang von Laufzeit und Approximationsfaktor (nicht FPTAS)[ACG,3.2]; Klasse FPTAS
• Schwächere Approximierbarkeit: von der Eingabelänge abhängige performance guarantee;
  Beispiel: $(\lfloor\ln n\rfloor+1)$-Approximation für MIN SET COVER und $(3n/\log_k n)$-Approximation für MIN GRAPH COLORING [ACG,4.1]
• Zwischen APX und PTAS: Asymptotische Approximationsschemata;
  Beispiel: MIN EDGE COLORING und MIN BIN PACKING [ACG,4.2]

Thema 4:

Allgemeine Approximationstechniken I

• Greedy Algorithmen; Beispiel: HLF-Algorithmus für MIN SCHEDULING ON IDENTICAL MACHINES oder MAX KNAPSACK oder
  MAX INDEPENDENT SET oder $\frac{1}{2}(\lceil\log n\rceil +1)$-Approximation für METRIC TSP [ACG,2.1]
• ``Sequentielle Algorithmen'' für Partitionierungsprobleme; Beispiel: MIN BIN PACKING oder MIN GRAPH COLORING [ACG,2.2]
• Lokale Suche; Beispiel: 2-Approximation für MAX CUT [ACG,2.3]
• Dynamische Programmierung; Beispiel: Approximationsschema für MAX KNAPSACK [ACG,2.5]

Thema 5:

Allgemeine Approximationstechniken II
(mit linearer Programmierung)

• Struktur von linearen Programmen mit Beispiel [GOE,LP.1-4]
• Simplexmethode [GOE,LP.5-7]
• Dualität [GOE,LP.9]
• NP-vollständigkeit des Problems INTEGER LINEAR PROGRAMMING [GJ,p.287]
• Integer Relaxation und Runden; Beispiel: 2-Approximation für WEIGHTED VERTEX COVER [ACG,2.4]
• Primal-Dual-Algorithmen; Beispiel: Effizientere 2-Approximation für WEIGHTED VERTEX COVER [ACG,2.4]

Thema 6:

Allgemeine Approximationstechniken III
(heuristische Methoden)

• Wiederholung: Lokale Suche; [ACG,2.3,10.3]
• Lokale Suche mit beschränkter Tiefe; Beispiel: TSP und EUCLIDEAN TSP [ACG,10.3]
• Lokale Suche mit variabler Tiefe; Beispiel: TSP und Kernighan-Lin-Algorithmus für MIN BALANCED CUT [ACG,10.3]
• Am Rande: Simulated Annealing, genetische Algorithmen und Tabu Search [ACG,10.4]

Thema 7:

Randomisierte Approximationsalgorithmen I

• Kurze Einführung in Randomisierung[ACG,2.6]
• Beispiel: randomisierte 2-Approximation für WEIGHTED VERTEX COVER [ACG,5.1]
• Derandomisierung; Beispiel: MAX WEIGHTED SAT [ACG,5.4]

Thema 8:

Randomisierte Approximationsalgorithmen II
(mit semidefiniter Programmierung)

• Einführung in Semidefinite Programmierung mit Beispielen [VB]
• Algorithmen mit semidefiniter Programmierung; Beispiel: MAX WEIGHTED CUT [ACG,5.3]

Literatur:

• [ACG]: Complexity and Approximation -- Combinatorial Optimization Problems and Their Approximability Properties, G. Ausiello, P. Crescenzi et. al.; Springer 1999
• [GOE]: Linear Programming, Teil der Advanced Algorithms Lecture Notes von M. Goemans, 1994
• [GJ]: Computers and Intractability -- A Guide to the Theory of NP-completeness, M. Garey, D. Johnson; Freeman 1979
• [VB]: Semidefinite Programming, L Vandenberghe, S. Boyd; SIAM Review März 1996

Organisatorisches:

Die Vorträge finden Donnerstags, ab 14:00 ct in Raum S2229 statt.
Den aktuellen Stand der Vortragstermine finden Sie hier.
Und hier gibt einige Tips zur Erstellung von Folien mit LaTeX.
Hinweise zur Gestaltung der Vorträge: Merkblatt zur Gestaltung eines Seminarvortrags