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 uns stattdessen effizientere Approximationsalgorithmen anschauen. Dabei wollen wir uns sowohl Probleme auf Punktmengen (z.B. closest pair, clustering) sowie auf Graphen (z.B. spanning trees, Euclidean TSP) anschauen, und verschiedene Methoden zum Entwurf von Approximationsalgorithmen kennenlernen (z.B. grids, sampling, reweighing).

Als Vorkenntnisse wird die Vorlesung “Algorithmen und Datenstrukturen” oder vergleichbare Kenntnisse erwartet.

• Vorlesung + Übung:
  • Dienstag, 10:15-14:00 Uhr, Raum 304, Otto-Hahn-Str. 14
• Beginn der Vorlesungen: Dienstag, 12. Oktober 2021

• Prüfungen (s. Modulbeschreibung sowie Folien der ersten Vorlesung):
  • mündlich
  • aktive Teilnahme (inkl. Präsentation eigener Lösungen)

• Vorlesungsfolien
• Das Buch “Geometric Approximation Algorithms” von Sariel Har-Peled. Online verfügbar hier

• Grids (Closest Pair): grids.pdf (2 Vorlesungen), blatt01.pdf
• Grids (-enclosing disk): blatt02.pdf
• Quadtrees quadtrees.pdf, blatt03.pdf
• WSPD wspd.pdf, blatt04.pdf
• clustering clustering.pdf, blatt05.pdf
• sampling e-nets-and-sampling.pdf, blatt06.pdf
• geometric set cover geometric-set-cover.pdf, blatt07.pdf
• discrepancy discrepancy.pdf, blatt08.pdf
• approximate nearest neighbors ann-1.pdf blatt09.pdf
• ring separator tree: sspd.pdf
• shifting point sets: shifting.pdf, blatt10.pdf, blatt11.pdf
• ANN via point location ann_balls.pdf, blatt12.pdf
• Approximate Voronoi diagrams avd.pdf, blatt13.pdf
• Coresets coresets.pdf, blatt14.pdf
• ETSP etsp_portals.pdf, akda-summary.pdf

Bei Fragen zu dieser Veranstaltung wenden Sie sich bitte an Kevin Buchin (bis November über die kevin.buchin@cs E-Mail Adresse)