Neuartige Approximationstechniken für Traveling Salesperson Probleme

• Antragsteller: Professor Dr. Tobias Mömke
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2015 bis 2019
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 277883503

Dieses Forschungsprojekt verfolgt die Absicht, das Wissen über Approximationsalgorithmen für das metrische Traveling Salesperson Problem (metrisches TSP) und verwandte Probleme voranzubringen.Das klassische TSP wird als Graphenproblem modelliert. Die Eingabe ist eine Menge von Orten (Knoten) und eine Menge von Straßen (Kanten) die diese Orte verbinden, mit Kosten (z.B. Distanz, Zeit) für jede Kante. Ziel ist es, einen Weg mit minimalen Gesamtkosten zu finden, der jeden Knoten genau einmal besucht und danach zurück zum Ursprungsort führt.Das metrische TSP ist eine Variante des TSP bei der die Kosten nichtnegativ und symmetrisch sind und die Dreiecksungleichung erfüllen. Der beste Polynomzeitalgorithmus für das metrische TSP ist der 1.5-Approximationsalgorithmus von Christofides aus dem Jahr 1976. Eine Verbesserung dieses Algorithmus zu finden ist nach wie vor ein wichtiges Problem. Die umfangreiche Forschung die in diesem Bereich unternommen wurde legt nahe, dass eine Verbesserung der Approximation bessere algorithmische Techniken voraussetzt. Jüngste Techniken, die für das verwandte graph-TSP und für die Pfad Version des metrischen TSP verwendet wurden, geben neue Hoffnung, endlich die Schwierigkeiten zu überwinden.Wir planen die Entwicklung neuer Approximationstechniken für das metrische TSP und dessen Varianten, wie z.B. graph-TSP. Wir wollen dieses Ziel schrittweise verflogen, indem wir einige der jüngsten Techniken verwenden um verbesserte Algorithmen für TSP Varianten und ähnliche Probleme zu finden, mit Kandidaten wie z.B. k-TSP, dem Minimum Latency Problem, und dem Problem minimale 2-verbundene Teilgraphen zu finden. Einiger dieser Techniken sind Sum of Squares, semidefinite Programmierung, iterative lineare Programmierung, Thin Spanning Trees, und Removable Pairings. Der Projektleiter spielte eine zentrale Rolle in der Entwicklung und Anwendung der zuletzt genannten Technik, Removable Pairings. Diese ergaben eine Verbesserung des vorher besten graph-TSP Resultats und sie werden im derzeit besten graph-TSP Algorithmus verwendet.Verbesserte Approximationsalgorithmen für die Hauptprobleme dieses Projekts zu finden würde weitreichende Auswirkungen im Bereich der Approximationsalgorithmen haben und hätte das Potential, das Lösen praktischer Probleminstanzen zu erleichtern, da TSP weite Anwendungen in Bereichen wie der Logistik, Genetik, industriellen Fertigung, Telekommunikation und Neurowissenschaft hat.Unabhängig davon ob wir es schaffen diese schwierigen Probleme zu lösen, werden die zu erwartenden neuen Techniken und Algorithmen des Projekts selbst nützlich sein und voraussichtlich die Entwicklung von Approximationsalgorithmen voranbringen, die sogar über den Umfangs dieses Projekts hinaus reicht.

• DFG-Verfahren: Sachbeihilfen