Servicenavigation

Detailseite

Zurück

Projekt Druckansicht

Neuartige Approximationstechniken für Traveling Salesman Probleme

Fachliche Zuordnung Theoretische Informatik
Förderung Förderung von 2020 bis 2024
Projektkennung Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 439637648
 
Erstellungsjahr 2025

Zusammenfassung der Projektergebnisse

Das Forschungsprojekt hat dazu beigetragen, das Wissen zu Techniken im Berich der kombinatorischen Optimierung zu erweitern, insbesondere zum Design von Approximationsalgorithmen. Mit dem Ziel, das metrische Traveling Salesman Problem besser zu approximieren, haben wir ein besseres Verständnis darüber entwickelt, wo die exakten Hürden liegen und Techniken entwickelt um mit diesen umzugehen. Der Projektantrag beinhaltete viele ambitionierte Ziele. Einige konkrete Ziele wurden vollständig erreicht und viele verwandte hochwertige Resultate wurden erzielt. Im folgenden beschränken wir uns auf die drei wichtigsten Resultate des Projekts. Ein besonders wichtiges erreichtes Ziel war, dass wir die best-mögliche Qualitätsgarantie für das Problem Unsplittable Flow on a Path erhalten haben, die in Polynomzeit zu erwarten ist. Diese Arbeit steht am Ende einer fortwährenden Forschungstätigkeit, die über einen langen Zeitraum zu einer großen Anzahl an hochrangigen Veröffentlichungen geführt hat; die Beteiligung des PIs an dieser Forschung begann im Jahr 2015 und während im Rahmen des Projekts Fortschritte zu erwarten waren, war eine vollständige Lösung des Problems zum Zeitpunkt der Antragstellung außer Reichweite. Ein zweites direktes Ziel des Antrags war es, eine verbesserte Approximationsgüte für eine Verallgemeinerung des Traveling Salesman Problems zu erhalten, die sich Ordered TSP nennt. Der im Projekt erhaltene Approximationsalgorithmus erreicht nicht nur das angestrebte Ziel, sondern führt eine neue Technik ein, die sich schon zum jetzigen Zeitpunkt als hilfreich für andere Resultate gezeigt hat, die der PI zusammen mit seinen Mitarbeitern nach Ende der Förderung erhalten hat. Gegen Ende der Förderung konnte der PI zusammen mit einer Koautorin ein wichtiges Resultat zum Euklidischen TSP erreichen. Die euklidische Ebene ist einer der natürlichsten Räume, die man sich vorstellen kann: Die Städte sind Punkte, die durch zwei Koordinaten (z.B. x und y) bestimmt sind und der Abstand zwischen zwei Punkten ist die Länge des Geradenabschnitts zwischen diesen beiden Punkten. In diesem Raum ist die beste Approximationsgüte, auf die wir in Polynomzeit hoffen können der Faktor (1 + ). Unser Beitrag ist ein Algorithmus, der (bis auf konstante Faktoren) die bestmögliche Laufzeit hat, die man erwarten kann: Die Laufzeit ist gleichzeitig linear in der Anzahl der als Eingabe gegebenen Punkte und optimal im Bezug zum Fehler soweit in der Literatur etablierte Vermutungen wahr sind. Desweiteren ist der Algorithmus relativ simpel – die Komplikationen liegen in der Analyse des Algorithmus. Aufgrund der Einfachheit des Algorithmus ist es nicht schwer, diesen zu implementieren. Das Ergebnis hat daher potentiellen praktischen Nutzen. Während es sich um eins der wichtigsten im Projekt erreichten Resultate handelt, ist dieses Ergebnis zur Zeit noch im Begutachtungsprozess.

Projektbezogene Publikationen (Auswahl)

 
 

Zusatzinformationen

© 2026 DFG Kontakt / Impressum / Datenschutz

Textvergrößerung und Kontrastanpassung