Online and multi-agent approximations for the traveling salesperson problem

In the classical traveling salesperson problem (TSP), we need to find a shortest possible tour that visits all points of a finite metric space. This constitutes one of the most extensively studied problems in combinatorial optimization. In this thesis, we study the TSP under additional restrictions such as incomplete information or restricted computational complexity. We consider several such settings and study online and offline approximation algorithms for them.

In the online graph exploration problem, a single agent needs to find a TSP tour in an initially unknown weighted graph, which is gradually learned over time. We prove a constant competitive ratio for this problem when restricted to minor-free graphs. This result encompasses and significantly extends the graph classes that were previously known to admit a constant competitive ratio. The main ingredient of our proof is that we find a connection between the particular exploration algorithm Blocking and the existence of light spanners. We also exploit this connection in the opposite direction to construct light spanners of bounded-genus graphs. Moreover, we prove that the competitive ratio of the online graph exploration problem is at least 4, even when restricted to subcubic planar graphs. This improves on the previously best known lower bound of 10/3. Additionally, we study the collaborative tree exploration problem, which is a variant of the exploration problem with multiple agents. We give a slightly improved bound on the competitive ratio of the classical algorithm Yo*.

In the tricolored Euclidean traveling salesperson problem, we are given three sets of points in the Euclidean plane and need to find three non-crossing tours, each covering one of the sets. In this problem, we address restrictions in computational complexity rather than on information. Our main contribution is a polynomial-time (5/3+ε)-approximation algorithm. For this, we generalize Arora's famous PTAS for the Euclidean TSP. One of its key ingredients is the "Patching Lemma", which is known to generalize to two non-crossing tours but not to three or more. We circumvent this issue by combining a conditional patching scheme for three tours and an alternative approach based on a weighted solution for two colors.

In the open online dial-a-ride problem, a single agent is tasked to serve transportation requests arriving online, subject to minimizing the completion time. We introduce the algorithm Lazy and give a tight analysis, proving that its competitive ratio is 2.457 on general metric spaces, and 2.366 on the half-line. This improves on the previously best known bound of 2.696 in these metric spaces.

Im klassischen Problem des Handlungsreisenden (TSP) soll eine kürzestmögliche Rundtour gefunden werden, die alle Punkte eines endlichen metrischen Raums besucht. Es zählt zu den am intensivsten untersuchten Problemen der kombinatorischen Optimierung. In dieser Arbeit betrachten wir Varianten des TSP unter zusätzlichen Einschränkungen, etwa unvollständiger Information oder begrenzter Rechenressourcen. Wir betrachten verschiedene solcher Szenarien und analysieren Online- und Offline-Approximationsalgorithmen.

Im Online-Graphenexplorationsproblem muss ein Agent eine TSP-Tour in einem anfangs unbekannten, gewichteten Graphen finden, der während der Exploration sukzessive erlernt wird. Wir beweisen, dass der kompetitive Faktor des Problems konstant ist, wenn es auf minorenfreie Graphen eingeschränkt wird. Dieses Resultat umfasst und erweitert die Graphenklassen, für die bisher ein konstanter kompetitiver Faktor bekannt war, signifikant. Die Kernidee des Beweises ist ein Zusammenhang zwischen dem Explorationsalgorithmus Blocking und der Existenz leichter Spanngraphen. Diese Verbindung nutzen wir auch in umgekehrter Richtung, um leichte Spanngraphen für Graphen mit beschränktem Genus zu konstruieren. Darüber hinaus zeigen wir, dass der kompetitive Faktor des Online-Graphenexplorationsproblems mindestens 4 beträgt, auch wenn das Problem auf subkubische planare Graphen eingeschränkt wird. Dies verbessert die bisherige untere Schranke von 10/3. Zudem untersuchen wir das kollaborative Explorationsproblem, eine Variante mit mehreren Agenten, und geben hierbei eine leicht verbesserte Schranke für den kompetitiven Faktor des klassischen Algorithmus Yo* an.

Im dreifarbigen Euklidischen TSP sind drei Punktmengen in der Euklidischen Ebene gegeben, und es müssen drei sich nicht kreuzende Rundtouren gefunden werden, die jeweils eine der Mengen abdecken. Anstelle der Informationsverfügbarkeit betrachten wir hier Einschränkungen bezüglich der Berechnungskomplexität. Unser Hauptresultat ist ein (5/3+ε)-Approximationsalgorithmus mit polynomialer Laufzeit. Hierfür verallgemeinern wir Aroras berühmtes PTAS für das Euklidische TSP. Eine seiner Kernideen ist das sogenannte "Patching Lemma", das sich auf zwei nicht kreuzende Touren verallgemeinern lässt, jedoch nicht auf drei oder mehr. Wir umgehen dieses Problem, indem wir entweder ein bedingtes Patching-Schema für drei Touren anwenden oder einen alternativen Ansatz auf Basis einer gewichteten Lösung für zwei Farben verwenden.

Im offenen Online-Dial-a-Ride-Problem müssen online eintreffende Transportanfragen so bedient werden, dass die Gesamtabschlusszeit minimiert wird. Wir führen dafür den Algorithmus Lazy ein und geben eine scharfe Schranke für seinen kompetitiven Faktor an: 2.457 in allgemeinen metrischen Räumen sowie 2.366 auf der Halbgeraden. Damit verbessern wir die bisher beste bekannte Schranke von 2.696 in diesen metrischen Räumen.