====== Modul Ausgewählte Kapitel der Algorithmik  (WiSe 2021/22) ======

| Veranstalter | Prof. Dr. Kevin Buchin |
| Modul          | Diplom, Master [[https://www.cs.tu-dortmund.de/nps/de/Studium/Ordnungen_Handbuecher_Beschluesse/Modulhandbuecher/Master_Inf/Vertiefungsmodule/Forschungsbereich_Algorithmen_und_Komplexitaet/INF-MSc-603.pdf|INF-MSc-603 (Informatik, Angewandte Informatik)]] | 
| Veranstaltungsart    | VO 2 + UE 2                 |
| Veranstaltungsnummer | [[https://www.lsf.tu-dortmund.de/qisserver/rds?state=verpublish&status=init&vmfile=no&publishid=194898&moduleCall=webInfo&publishConfFile=webInfo&publishSubDir=veranstaltung|042605]]                   |
| Moodle | ab November|

===== Inhalt und Themen =====
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.


===== Ort und Zeit =====

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

===== Prüfungen =====

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


===== Materialien =====

  * Vorlesungsfolien
  * Das Buch "Geometric Approximation Algorithms" von Sariel Har-Peled. Online verfügbar [[https://sarielhp.org/book/|hier]]

===== Themen =====

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

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