论文标题
更快的定向算法和$ K $ -TSP
Faster Algorithms for Orienteering and $k$-TSP
论文作者
论文摘要
我们认为欧几里得空间中的根源定向问题：给定$ n $ points $ p $ in $ \ m arthbb r^d $，p $中的root Point Point $ s \和预算$ \ Mathcal b> 0 $，找到一条从$ s $开始的路径，最多可以从$ \ nthcal b $ wistits of Mathcal b $，以及$ p $ $ P $ p $ p $ p $。该问题已知是NP- hard，因此我们研究$（1-δ）$ - 近似算法。由于Chen and Har-Peled（2008），以前的多项式时间近似方案（PTA）在时间$ n^{o（d \ sqrt {d}/δ）}（\ log n）^{（d/δ）^{（d/δ）^{o（d）}} $上，并在时间上加快了一个问题。我们的主要贡献是一个PTA，其时间复杂性显着提高为$ n^{o（1/δ）}（\ log n）^{（d/δ）^{o（d）}} $。 近似定向问题的已知技术是将其减少到解决$ 1/δ$相关的实例的$ k $ -tsp（a $ k $ -tsp Tour是访问至少$ k $点）的实例。但是，此减少的$ K $ -TSP巡回赛必须实现一定的过量保证（即，它们的长度只能按比通常的$（1+δ）$ - 近似的最佳参数成比例超过最佳长度）。我们的主要技术贡献是改善这些$ k $ -TSP变体的运行时间，尤其是在其对尺寸$ d $的依赖中。确实，即使对于中等大的维度，我们的运行时间也是多项式，大约$ d = o（\ log \ log \ log n）$而不是$ d = o（1）$。
We consider the rooted orienteering problem in Euclidean space: Given $n$ points $P$ in $\mathbb R^d$, a root point $s\in P$ and a budget $\mathcal B>0$, find a path that starts from $s$, has total length at most $\mathcal B$, and visits as many points of $P$ as possible. This problem is known to be NP-hard, hence we study $(1-δ)$-approximation algorithms. The previous Polynomial-Time Approximation Scheme (PTAS) for this problem, due to Chen and Har-Peled (2008), runs in time $n^{O(d\sqrt{d}/δ)}(\log n)^{(d/δ)^{O(d)}}$, and improving on this time bound was left as an open problem. Our main contribution is a PTAS with a significantly improved time complexity of $n^{O(1/δ)}(\log n)^{(d/δ)^{O(d)}}$. A known technique for approximating the orienteering problem is to reduce it to solving $1/δ$ correlated instances of rooted $k$-TSP (a $k$-TSP tour is one that visits at least $k$ points). However, the $k$-TSP tours in this reduction must achieve a certain excess guarantee (namely, their length can surpass the optimum length only in proportion to a parameter of the optimum called excess) that is stronger than the usual $(1+δ)$-approximation. Our main technical contribution is to improve the running time of these $k$-TSP variants, particularly in its dependence on the dimension $d$. Indeed, our running time is polynomial even for a moderately large dimension, roughly up to $d=O(\log\log n)$ instead of $d=O(1)$.
