Lehrstuhl Mathematik & InformatikGeometrische Approximationsalgorithmen Winter 19/20
| LVR-Nr: | 150 361 |
|---|---|
| Veranstaltung: | Geometrische Approximationsalgorithmen 2 std. IA 1/177 Di 14.00-16.00 |
| Dozentin: | Maike Buchin |
| Übungen: |
Bernhard Kilgus 2 Std. alle zwei Wochen IA 1/135 Fr 12.00 - 14.00 Die erste Übung findet am 18.10. statt. |
Kommentar
In der Vorlesung werden Approximationsalgorithmen für geometrische Probleme besprochen. Für manche geometrische Probleme haben bekannte exakte Algorithmen eine hohe Laufzeit, manche davon sind sogar NP-schwer. Für diese Probleme wollen wir stattdessen effiziente Approximationsalgorithmen sehen. Dabei betrachten wir verschiedene Probleme auf Punktmengen (z.B. closest pair, clustering, triangulation, Euclidean TSP) und verwenden verschiedene Methoden zum Entwurf von Approximationsalgorithmen (z.B. snapping to grids, sampling, reweighing).
Voraussetzungen
Es werden grundlegende Kenntnisse über Algorithmen und Datenstrukturen erwartet, sowie grundlegende Kenntnisse der Stochastik.
Literatur
Die Vorlesung orientiert sich an dem Buch "Geometric Approximation Algorithms ", von Sariel Har-Peled (1. Auflage, 2011, American Mathematical Society).
Materialien
Übungsblätter
Präsenzblätter
- Blatt 1
- Blatt 2
- Blatt 3
- Blatt 4
- Blatt 5
- Blatt 6
- Blatt 7
- Maike Buchin, IB 3/151
- Bernhard Kilgus, IB 3/149
Prüfungen
Die Prüfungsanmeldung erfolgt nach den Regeln des für Sie zuständigen Prüfungsamtes.
Termine für mündliche Prüfungen stehen am Di, den 11.2. und voraussichtlich am Di, den 31.3. zur Verfügung. Bitte lassen Sie sich vor der Anmeldung zur Prüfung eine Uhrzeit von Bernhard Kilgus geben.