论文标题
分布良好双曲线TSP的准多项式算法
A quasi-polynomial algorithm for well-spaced hyperbolic TSP
论文作者
论文摘要
我们在高斯曲率$ -1 $的双曲线平面上研究旅行推销员问题。令$α$表示任何两个输入点之间的最小距离。使用新的分隔符定理和新的重新路由参数，我们给出了$ n^{o（\ log^2 n）\ max（1,1/α）} $算法的双曲线TSP。如果$α$至少是一个绝对常数，则这是准级别时间的时间，并且会增长到$ n^{o（\ sqrt {n}）} $，因为$α$减少到$ \ log^2 n/\ sqrt {n} $。 （对于$α$的较小值，我们可以使用Hwang等人（1993）的基于平面的算法，该算法的运行时间为$ n^{o（\ sqrt {n}）} $。
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^2 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(\sqrt{n})}$ as $α$ decreases to $\log^2 n/\sqrt{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(\sqrt{n})}$.)
