License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SoCG.2020.55
URN: urn:nbn:de:0030-drops-122135
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12213/
Kisfaludi-Bak, Sándor
A Quasi-Polynomial Algorithm for Well-Spaced Hyperbolic TSP
Abstract
We study the traveling salesman problem in the hyperbolic plane of Gaussian curvature -1. Let α denote the minimum distance between any two input points. Using a new separator theorem and a new rerouting argument, we give an n^{O(log² n)max(1,1/α)} algorithm for Hyperbolic TSP. This is quasi-polynomial time if α is at least some absolute constant, and it grows to n^O(√n) as α decreases to log² n/√n. (For even smaller values of α, we can use a planarity-based algorithm of Hwang et al. (1993), which gives a running time of n^O(√n).)
BibTeX - Entry
@InProceedings{kisfaludibak:LIPIcs:2020:12213,
author = {S{\'a}ndor Kisfaludi-Bak},
title = {{A Quasi-Polynomial Algorithm for Well-Spaced Hyperbolic TSP}},
booktitle = {36th International Symposium on Computational Geometry (SoCG 2020)},
pages = {55:1--55:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-143-6},
ISSN = {1868-8969},
year = {2020},
volume = {164},
editor = {Sergio Cabello and Danny Z. Chen},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12213},
URN = {urn:nbn:de:0030-drops-122135},
doi = {10.4230/LIPIcs.SoCG.2020.55},
annote = {Keywords: Computational geometry, Hyperbolic geometry, Traveling salesman}
}
|
Keywords: |
|
Computational geometry, Hyperbolic geometry, Traveling salesman |
|
Collection: |
|
36th International Symposium on Computational Geometry (SoCG 2020) |
|
Issue Date: |
|
2020 |
|
Date of publication: |
|
08.06.2020 |
