Many Visits TSP Revisited

Medientyp: E-Artikel; Elektronischer Konferenzbericht; Sonstige Veröffentlichung

Titel: Many Visits TSP Revisited

Beteiligte: Kowalik, Łukasz [VerfasserIn]; Li, Shaohua [VerfasserIn]; Nadara, Wojciech [VerfasserIn]; Smulewicz, Marcin [VerfasserIn]; Wahlström, Magnus [VerfasserIn]

Erschienen: Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2020

Sprache: Englisch

DOI: https://doi.org/10.4230/LIPIcs.ESA.2020.66

Schlagwörter: many visits traveling salesman problem ; exponential algorithm

Entstehung:

Anmerkungen: Diese Datenquelle enthält auch Bestandsnachweise, die nicht zu einem Volltext führen.

Beschreibung: We study the Many Visits TSP problem, where given a number k(v) for each of n cities and pairwise (possibly asymmetric) integer distances, one has to find an optimal tour that visits each city v exactly k(v) times. The currently fastest algorithm is due to Berger, Kozma, Mnich and Vincze [SODA 2019, TALG 2020] and runs in time and space O*(5ⁿ). They also show a polynomial space algorithm running in time O(16^{n+o(n)}). In this work, we show three main results: - A randomized polynomial space algorithm in time O*(2^n D), where D is the maximum distance between two cities. By using standard methods, this results in a (1+ε)-approximation in time O*(2ⁿε^{-1}). Improving the constant 2 in these results would be a major breakthrough, as it would result in improving the O*(2ⁿ)-time algorithm for Directed Hamiltonian Cycle, which is a 50 years old open problem. - A tight analysis of Berger et al.’s exponential space algorithm, resulting in an O*(4ⁿ) running time bound. - A new polynomial space algorithm, running in time O(7.88ⁿ).

Zugangsstatus: Freier Zugang

Nur in Feld suchen:

Zuletzt gesuchte Begriffe: