Das Traveling Salesman Problem (TSP) ist wohl das berühmteste kombinatorische Optimierungsproblem. In beliebigen endlichen Metriken kann man in polynomieller Zeit eine Rundreise berechnen, die höchstens anderthalbmal länger ist als eine optimale. Seit Jahrzehnten versucht man vergeblich, diesen bekannten Algorithmus von Christofides [1976] zu verbessern. In den letzten zwei Jahren gab es nun erstmals Fortschritte bei einem wichtigen Spezialfall: dem graphischen TSP. In diesem Seminar werden wir diese neuen Ergebnisse und einige verwandte Arbeiten behandeln. Grundlage sind überwiegend aktuelle Originalarbeiten. Dieses Seminar ist daher vielleicht anspruchsvoller, aber auch interessanter als üblich.
| Nr. | Probevortrag 12 Uhr c.t. |
Vortrag 14 Uhr c.t. |
Name | Thema | Betreuung |
|---|---|---|---|---|---|
| 1 | 15.10. | 29.10. | Lena Durst | Christofides, Subtour Relaxation, Graphic TSP | Jan Schneider |
| 2 | 22.10. | 5.11. | Sophie Spirkl | Random Sampling for the Asymmetric TSP | Michael Gester |
| 3 | 29.10. | 12.11. | Marvin Teichmann | Improving Christofides for the Graphic TSP | Daniel Rotter |
| 4 | 5.11. | 19.11. | Ines Exner | Removable Pairings and Subcubic Graphs | Daniel Rotter |
| 5 | 12.11. | 26.11. | Felizia Reinsch | Ear-Decompositions and T-joins | Michael Gester |
| 6 | 19.11. | 3.12. | Mirko Wilde | Optimizing Ears for the Graphic TSP | Jan Schneider |
| 7 | 26.11. | 10.12. | Siad Daboul | 7/5-Approximation for Graphic TSP | Jan Schneider |
| 8 | 3.12. | 17.12. | Stefan König | Improving Christofides for the s-t-Path-TSP | Ulrike Suhl |
| 9 | 10.12. | 7.1.2013 | Timm Behner | Inapproximability | Ulrike Suhl |
| 10 | 17.12. | 14.1. | Tom Mechandjijski | Eight Fifth Approximation for TSP Paths | Ulrike Suhl |