Im Wintersemester 22/23 beschäftigt sich das Seminar mit der Suche nach Wegen in Graphen. Lösungen zu diesen Fragen werden benötigt, um effizient Pakete an Kunden zu liefern oder schnell an einen Zielort zu gelangen. Algorithmisch kann man diese Fragestellungen als Optimierungsprobleme auf Graphen formulieren (z.B. TSP, Vehicle Routing Problem, Latency Problem).

In diesem Bereich gab es in den letzten Jahren viele neue Entwicklungen. Das Seminar beschäftigt sich damit, einen Überblick über den aktuellen Stand der Forschung zu geben.

Mögliche Themen sind beispielsweise:

• TSP Approximationen von 1976 bis 2021 - Christofides, Serdyukov, Karlin, Klein, Oveis Gharan
• History of TSP
• Capacitated Vehicle Routing: Viele kurze Routen statt einer langen
• Exakte Lösungen für das TSP Problem

Im Seminar wird der typische Ablauf einer Konferenz simuliert: Nachdem zu Beginn die Themen verteilt wurden, arbeiten sich alle Teilnehmenden in ihr jeweiliges Thema ein, und verfassen einen ersten Entwurf ihrer Arbeit. Im weiteren Verlauf haben die Studierenden die Möglichkeit, konstruktives Feedback zu den Arbeiten der anderen zu geben und im Gegenzug Feedback zur eigenen Arbeit zu erhalten. Den Abschluss bildet dann ein Vortrag sowie die Abgabe der finalen Fassung der Arbeit.