文章基本信息

标题：A Quasi-Polynomial Algorithm for Well-Spaced Hyperbolic TSP
本地全文：下载
作者：S{'a}ndor Kisfaludi-Bak
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：164
页码：55:1-55:15
DOI：10.4230/LIPIcs.SoCG.2020.55
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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(â^Sn) as Î± decreases to logÂ² n/â^Sn. (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(â^Sn).)
关键词：Computational geometry; Hyperbolic geometry; Traveling salesman