Seminar: Approximationsalgorithmen
Im Seminar beschäftigen wir uns mit Approximationsalgorithmen für schwierige Probleme. Für viele kombinatorische Optimierungsprobleme wissen wir, dass diese NP-schwierig sind. Einen schnellen Algorithmus, der uns eines dieser Probleme exakt löst, werden wir daher wahrscheinlich nicht finden. Wir wollen uns für verschiedene bekannte Graphen- und Optimierungsprobleme - wie bspw. das Traveling-Salesman-, das Bin Packing- oder das Rucksack-Problem - Algorithmen anschauen, die diese zwar nicht exakt, aber approximativ mit einer gewissen, beweisbaren Approximationsgüte lösen.
Das Seminar wird als Blockseminar in der letzten Vorlesungswoche stattfinden.
Termine:
- Mo., 10.07.23, 9:00 - 13:00
- Di., 11.07.23, 8:00 - 12:00
- Mi., 12.07.23, 12:00 - 16:00
Ort:
- Seminarraum 1.421, Sibille-Hartmann-Str. 6
Anmeldung / Vorbesprechung:
Die Vorbesprechung hat bereits stattgefunden. Alle Studierenden, die im Anschluss einen Seminarplatz von mir erhalten haben, melden sich bitte in der Anmeldephase (03.03. - 20.03.) über KLIPS an.
Vorträge:
Der Vortrag soll ca. 45 Minuten dauern, an deren Anschluss Zeit für die Beantwortung von eventuellen Fragen und eine kurze Diskussion bleibt. Weiterhin soll der Vortrag größtenteils auf Whiteboard präsentiert werden. Folien auf dem Beamer sollen nur unterstützend (bspw. für komplexe Grafiken oder wichtige Definitionen) verwendet werden. Die Ausgabe eines "Handouts" begleitend zum Vortrag (nicht zu verwechseln mit der "Ausarbeitung", s.u.) ist nicht zwingend vorgesehen.
Ausarbeitung:
Zusätzlich zu dem Vortrag soll eine kurze Ausarbeitung von ca. 4 Seiten (Richtwert: DinA4, 12pt) erstellt werden. Diese soll den Inhalt des Vortrags zusammenfassen. Eine grobe Fassung der Ausarbeitung kann ebenfalls bei der Vorbesprechung helfen. Die endgültige Fassung der Ausarbeitung muss eine Woche vor dem eigentlichen Vortragstermin abgegeben werden. Die Ausarbeitung sollte mit LaTeX erstellt werden.
Literatur:
- V. Vazirani. Approximation Algorithms. Springer (2001)