Hauptseminar: Approximationsalgorithmen

[Zusammenfassung] [Themenliste] [Anmeldung] [Vorbesprechung] [Termine] [Hinweise] [Literatur]

Zusammenfassung

Viele Optimierungsprobleme, die in praktischen Anwendungen sehr oft vorkommen, sind NP-hart. Wenn nun angenommen wird, dass die Problemklassen P und NP nicht gleich sind, dann ist die Lösung dieser Probleme aus praktischer Hinsicht nicht möglich - sie würde sehr viele Ressourcen (Zeit und evtl. Speicherplatz) in Anspruch nehmen. Aus diesem Grund ist man daran interessiert, effiziente Algorithmen anzugeben, mit denen sich die exakte Lösung dieser Probleme approximieren lässt. Wichtige Fragestellungen, die in diesem Zusammenhang betrachtet werden, sind zum einen die Approximationsgüte, die die garantierte maximale Abweichung von der optimalen Lösung beschreibt, und zum anderen die Frage, ob ein gegebenes Problem überhaupt innerhalb einer gegebenen Approximationsgüte approximierbar ist.

Das Hauptseminar wird sich grob in 3 Themenbereiche gliedern. Die Theorie der Approximationsalgorithmen wird mit einen kleinen Ausflug in die Komplexitätstheorie für Optimierungsprobleme eingeleitet.
Der nächste Themenbereich, den man mit dem Stichwort Approximationstechniken betiteln könnte, gibt einen Einblick in die verschiedenen Techniken, die verwendet werden, um Approximationsalgorithmen mit bestimmten Gütekriterien zu entwerfen. Die auf der Theorie der Linearen Programmierung basierenden Verfahren (LP-Rounding und Primal-Dual-Schemata) werden im Vordergrund stehen, wobei andere Ansätze, wie z.B. heuristische Verfahren, nicht ausser Acht gelassen werden. In allen Vorträgen soll ein grundlegendes Problemverständnis vermittelt werden, wobei der aktuelle Stand der Forschung - soweit möglich - nicht unbeachtet bleiben darf.
In diesem Sinne werden im dritten und letzten Themenbereich exemplarisch verschiedene NP-harte Optimierungsprobleme betrachtet und einzelne Resultate im Zusammenhang mit Approximationsalgorithmen vorgestellt, die erst kürzlich veröffentlicht worden sind.

Themenliste:

Titel	Inhalt	Literatur
Einführung: von NPO bis APX	Inhalt: NPO, Definition: Approximationalgorithmus, Die Klasse APX, Erste Technik: Lower-bounding OPT, nicht-Approximierbarkeit, Die Gap-Technik	[AA03], Kapitel 1, [ACG99], Kapitel 3.1
Die Klassen PTAS und FPTAS	PTAS, FPTAS, Peudo-polynomielle Algorithmen, Transformation eines pseudo-polynomieller Algorithmus in ein FPTAS: Knapsack, PTAS für BinPacking	[AA03], Kapitel 8,9, [ACG99], Kapitel 3.2,3.3
Approximationserhaltende Reduktionen und Vollständigkeiten	Inhalt: Approx.-Erhaltende Reduktionen, Die Klasse MAX-SNP, Vollständigkeiten	[ACG99], Kapitel 8, [Pap94]
Einführung in die Lineare Programmierung	Inhalt: LP, ILP, LP-Duality, Relaxierung, Complementary Slackness. Literatur:	[AA03], Kapitel 12, [LIV]
Approximation via LP am Beispiel SetCover	Inhalt: Greedy SetCover & Layering & Analyse per DualFitting, LP-rounding für Setcover, Primal-Dual-Schema für SetCover	[AA03], Kapitel 13,14,15
Random Knapsack	Algorithmus von Nemhauser-Ullmann im stochastischen Modell	[AA03],[Bei03],[Bei04]
Maximum Satisfiability		[AA03], Kapitel 16, [Yan92]
Shortest Common Superstring	Ein 2 1/2 -Approximationsalgorithmus für das Shortest Common Superstring Problem	[AA03], Kapitel 7, [Swe99]
Maximum Asymetric TSP	Ein 8/13 -Approximationsalgorithmus für das Maximum Asymetric TSP Problem	[AA03], [BLä04]
Euclidian TSP	Die Arbeiten von S. Arora zum Euclidian TSP Problem	[AA03], Kapitel 11 und zug. Paper
Pipage Rounding	Bei Pipage Rounding handelt es sich um eine deterministische Rundungstechnik für Approximationsalgorithmen, welche auf LP-Formulierungen basieren. Diese Technik soll am Beispiel von Maximum Covering vorgestellt werden	[Age]
Average Performance of Greedy Algorithms	"Die Härte von NP-harten Problemen liegt in einigen wenigen, nicht repräsentativen Probleminstanzen, die meisten Instanzen lassen sich viel einfacher lösen, beispielsweise mit Hilfe eines Greedy-Algorithmus." Diese Aussage wurde in der vorliegenden Arbeit beleuchtet.	[Fla05]

Anmeldung

Interessenten/innen können sich bei der Vorbesprechung oder vorab per Email an eckhardt 'that at' in 'dot' tum 'dot' de mit Subject "Approximationsalgorithmen (Anmeldung)" anmelden. In der E-Mail sollen folgende Informationen enthalten sein:

Name, Vorname
Studiengang und Studienfach
Semester
E-Mail (nur Adressen @in.tum.de)
bevorzugtes Thema

Bücher:
[AA03]	Vijay V. Vazirani Approximation Algorithms, Springer, 2003, ISBN 3540653678
[ACG99]	G. Ausiello, P. Crescenzi, G. Gambosi, V.Kann A. Marchetti-Spaccamely, M. Protasi Complexity and Approximation, Springer, 1999, ISBN 3540654313
[Pap94]	C.H. Papadimitriou Computational Complexity, Addison-Wesley, 1994
Artikel:
[Fla05]	Abraham D. Flaxman, Alan M. Frize, Juan C. Vera On the Average Case Performance for Some Greedy Approximation Algorithms For the uncapacitated FAcility Location Problem , Proceedings ACM STOC'05, pp. 441-449,2005.
[Age]	Ageev, Sviridenko On the Pipage Rounding: A New Method for Constructing Algorithms with Proven Performance Guarantee, Technical Report
[Swe99]	Z. Sweedyk A 2 1/2 - approximation algorithm for shortest common superstring, SIAM Journal of Computing, Vol 29, No. 3, pp. 954-986,1999
[Bei03]	Beier, Vöcking Random Knapsack in Expected Polynomial Time, Proceedings STOC '03, pp. 232-241,2003
[Bei04]	Beier, Vöcking Probabilistic Analysis of Knapsack Core Algorithms , Proceedings SODA '04, p. 468-477, 2004
[Yan92	M. Yannakakis On the approximation of maximum satisfiability , Proceedings SODA '92 , ACM, pp. 1-9, 1992
[Blä04]	Markus Bläser An 8/13-approximation algorithm for the asymetric maximum TSP , Journal of Algorithms 50, pp. 23-48,2004

Stefan Eckhardt

Last modified: Tue Jul 12 15:17:47 2005