Das sogenannte Traveling-Salesman-Problem (TSP, auch Problem des Handlungsreisenden genannt) ist wahrscheinlich das bekannteste Problem der Kombinatorischen Optimierung. Es ist leicht zu beschreiben: ,,Plane eine möglichst kurze Rundreise durch eine gegebene Menge von Städten.`` Interessant wird das TSP vor allem dadurch, daß das Problem trotz dieser einfachen Beschreibung nur sehr schwer zu lösen ist, da es zur Klasse der sogenannten NP-schweren Probleme gehört. Wissenschaftliche Ergebnisse am TSP haben schon mehrfach zu Durchbrüchen bei theoretischer wie praktischer Forschung in der Optimierung geführt. So konnte erst vor kurzem von Arora und Mitchell gezeigt werden, daß sich für geometrische TSP-Instanzen (in denen die Städte Punkten im Raum mit ihren geometrischen Distanzen entsprechen) sogenannte polynomielle Approximationsschemata existieren - d.h., für jede beliebige Genauigkeit gibt es in einem bestimmten Sinne schnelle Algorithmen, die eine Optimallösung gut approximieren.
Vom mathematischen Standpunkt erscheint das sogenannte Maximum-TSP eng verwandt: Hier geht es darum, eine längste Rundreise zu finden. Tatsächlich sind die betrachteten graphentheoretischen Objekte (sogenannte Hamiltonkreise) dieselben, und es ist leicht zu zeigen, daß das Maximum-TSP im allgemeinen ebenfalls NP-schwer ist. Nachdem Barvinok vor einigen Jahren für geometrische Instanzen ein polynomielles Approximationsschema entwickeln konnte, war es eine echte Sensation, als ihm im Jahre 1998 zusammen mit Johnson, Woeginger und Woodroofe der Nachweis gelang, daß bei bestimmten gängigen Abstandsmaßen in Räumen konstanter Dimension polynomielle Algorithmen existieren. Dazu gehören z.B. die sogenannten Manhattan-Metriken, bei denen die Abstände für Wege parallel zu den Koordinatenachsen gemessen werden. Dagegen war die Komplexität des Maximum-TSP für die gewöhnliche euklidische Metrik im zwei- oder mehrdimensionalen Raum ein offenes Problem.
Zunächst gelang uns durch einen Beweis der NP-Schwere für das Euklidische Maximum-TSP im dreidimensionalen Raum die Lösung des Problems von Barvinok et al. und damit der Nachweis, daß selbst für ganz natürliche geometrische Optimierungsprobleme die algorithmische Schwierigkeit ausschließlich von der Geometrie des Abstandsmaßes abhängen kann statt nur von der Kombinatorik des Problems.
Für den Fall von Manhattan-Distanzen in der Ebene entwickelten wir dann sogar noch einen einfachen Algorithmus mit linearer, also schnellstmöglicher Laufzeit. Dieses überraschende Resultat unterstreicht die wichtige Rolle der Geometrie in der Behandlung kombinatorischer Optimierungsprobleme.
