Seminar

Approximationsalgorithmen für schwere Probleme

Grund- und Hauptstudium Informatik und Mathematik

Beginn: Donnerstag, 16. 04. 98    12.15 Uhr,   SR 511

23. 04. 98, 30. 04. 98: Einfhrung zur Approximation bei schweren Problemen

Zur Auswahl stehende Vortragsthemen (Vorträge ab 07. 05. 98):

Approximationsalgorithmen fr NODE COVER und TSP
- CH. PAPADIMITRIOU / K. STEIGLITZ: Combinatorial Optimization Prentice-Hall 1982, 406-418 (auch russische �ersetzung vorh.)
Approximationsalgorithmen fr KP. Negative Resultate bei CLIQUE
- CH. PAPADIMITRIOU / K. STEIGLITZ: Combinatorial Optimization Prentice-Hall 1982, 419-431
Garantierte Leistungen von Approximationsalgorithmen
- M.R. GAREY / D.S. JOHNSON: Computers and Intructability W.H. Freeman and Company. New York 1979, 121-137
Mindestfehler von Approximationsalgorithmen fr NPC-Probleme
- M.R. GAREY / D.S. JOHNSON: Computers and Intructability W.H. Freeman and Company. New York 1979, 137-151
Approximationsalgorithmen fr unabh�gige Mengen in speziellen Graphen
- M.M. HALLDORSSON / J. RADHAKRISHNAN: Greed is good: Approximating Independent Sets in Sparse and Bounded-degree Graphs STOC 1994 Montral, Quebec, Canada, 439-448
Wann sind Greedy-Algorithmen zum Finden unabh�giger Mengen gut?
- H.L. BODLAENDER / D.M. THILIKOS / K. YAMAZAKI: It is Hard to Know when Greedy is Good for Finding Independent Sets Utrecht, the Netherlans 1997, 1-9
L�ung kombinatorischer Probleme durch Greedy-Algorithmen
- Y. CARO / A. SEB�/ M. TARSI: Recognizing Greedy Structures Journal of Algorithms 20, 1996, 137-156
Beweisverifikation und effiziente Approximierbarkeit - PCP-Theorie
- S. ARORA u.a.: Proof Verification and Hardness of Approximation Problems 1992 IEEE, 14-23
(fr 3-4 Studenten) Approximative L�ung von NP-Optimierungsproblemen - eine fundamentale Studie
- G. AUSIELLO / P. CRESCENZI / M. PROTASI: Approximate solution of NP optimization problems 1995 - Elsevier Science B.V. TCS 150 , 1-55
Zusammenhangsprobleme in Graphen und approximative L�ungsm�lichkeiten
- A. BLEY: Node-Disjoint Length-Restricted Paths Diplomarbeit, TU Berlin 1997 (ausgew�lte Abschnitte)

Bemerkungen:
Das Seminar kann in Form von Projekt- und Diplomarbeiten fortgesetzt werden (z.B. in Verbindung mit praktischer Implementierung von Algorithmen).

R. Winter, R. Stiebe