Dozent: Stefan Kirchner
Termine
Beginn der Vorlesung: 15.04.2005.| PS | Freitag | 11:00 - 13:00 | RUD 25, 4.112 |
|---|
Zuordnung
- Grundstudium, Proseminar
Inhalte und Lernziele
Viele in der Praxis auftretenden Optimierungsprobleme können nach heutigem Kenntnisstand nicht exakt in effizienter Zeit gelöst werden. Da sie dennoch gelöst werden sollen bzw. müssen, werden oft Heuristiken eingesetzt, die deutlich schneller sind, aber in der Regel die optimale Lösung verfehlen und eine Lösung liefern, die (hoffentlich) von der optimalen Lösung "nicht zu weit" entfernt ist. Approximationsalgorithmen zeichnen sich dadurch aus, daß sie dieses "nicht allzu weit" näher einschränken. Genauer werden sie duch zwei Eigenschaften charakterisiert:- sie haben polynomiale Laufzeit
- deren Lösung liegt maximal einen konstanten Faktor von der optimalen Lösung entfernt
Zumeist sind die Algorithmen relativ einfach zu verstehen und die Hauptschwierigkeit liegt darin, die letztere Eigenschaft nachzuweisen. In diesem Seminar werden nach einer kurzen Einführung in die Komplexitätstheorie für einige Probleme Approximationsalgorithmen und deren Analyse vorgestellt. Am Ende des Seminares werden wir auch auf Probleme zu sprechen kommen, die nicht gut approximierbar sind. Ein weiteres Ziel in diesem Seminar besteht darin, zu lernen wie gute Vorträge gehalten werden und wie geeignete Präsentationsmittel eingesetzt werden können.
Voraussetzungen
- keine: Literatur ist jedoch überwiegend auf Englisch.
Vortragsthemen
- Grundlegende Begriffe aus der Komplexitätstheorie; Klassifikationen von Approximationsalgorithmen
- Matchings
- Minimal spannende Bäume
- TSP: Christofides-Heuristik und euklidisches TSP
- Steinerbäume MST-Heuristik; k-Steiner-Bäume
- Shortest Common Superstring
- Bin-Packing
- SAT-Algorithmen
- Kantenfärbung
- Metrisches k-center Problem
- Set Cover
- Nichtapproximierbarkeitsresultate
Literatur
- , Introduction to Algorithms
- , Approximation Algorithms
- , Approximation Algorithms for NP-hard Problems
