Exact and approximation algorithms for many-visits travelling salesperson problems

Link:
Autor/in:
Beteiligte Person:
  • Mnich, Matthias
Verlag/Körperschaft:
Hamburg University of Technology
Erscheinungsjahr:
2022
Medientyp:
Text
Schlagworte:
  • traveling salesman problem
  • approximation algorithms
  • graph algorithms
  • combinatorial optimization
  • matroid theory
  • 510: Mathematik
Beschreibung:
  • Das Problem des Handlungsreisenden mit mehrfachen Besuchen ist eine natürliche Verallgemeinerung des Problems des Handlungsreisenden. Gegeben ist hierbei eine Reihe von Städten mit ihren paarweisen Abständen und eine geforderte Anzahl an Besuchen für jede Stadt. Das Ziel ist es zwischen zwei vorgegebenen Städten eine Reisestrecke minimaler Kosten zu finden, die jede Stadt genau so oft besucht, wie es gefordert ist. In dieser Arbeit stellen wir zunächst einen exakten Algorithmus vor, welcher eine optimale Lösung berechnet und dabei, abhängig von der Größe der Eingabe, exponentiell viel Zeit aber nur polynomiell viel Speicherplatz benötigt. Die Zeit- und Speicherplatzkomplexität ist dabei asymptotisch optimal. Darüber hinaus präsentieren wir eine effiziente 1,5-Approximation unter metrischen Entfernungskosten sowie Approximationen mit konstanter Güte für verschiedene Varianten des Problems mit mehreren Reisenden.
Lizenzen:
  • info:eu-repo/semantics/openAccess
  • https://creativecommons.org/licenses/by/4.0/
Quellsystem:
TUHH Open Research

Interne Metadaten
Quelldatensatz
oai:tore.tuhh.de:11420/11917