论文标题
近似算法和硬度$ n $ - 最短路径和最短周期
Approximation Algorithms and Hardness for $n$-Pairs Shortest Paths and All-Nodes Shortest Cycles
论文作者
论文摘要
我们研究了带有$ n $节点和$ m $边缘的图表上两个相关问题的近似性：$ n $ - 最短路径（$ n $ -psp），其中的目标是找到$ o（n）$预先指定的pairs pairs之间的最短路径，所有节点最短周期（ANSC），以及通过每个节点通过每个节点的纽带。大约$ n $ -PSP先前已经进行了研究，主要是在距离甲壳的背景下。我们询问一个问题，即与使用距离甲骨文或所有对最短路径（APSP）相比，是否可以更快地求解$ n $ -psp。先前还研究了ANSC，但仅根据精确的算法而不是近似。我们对$ n $ -PSP和ANSC的近似性进行了详尽的研究，提供了各种算法和有条件的下限，这些算法和有条件的下限在运行时间和近似比之间进行了差异。 我们条件下限结果的一个亮点是，对于任何整数$ k \ ge 1 $，在组合$ 4K $ -CLICE的假设下，没有组合算法对于未加权的$ n $ -psp的组合算法均优于$ 1+1+1+1+1+1/k $的组合算法$ O（m^{2-2/（k+1）} n^{1/（k+1）-ε}）$时间。这几乎与Agarwal（2014）结果所隐含的上限相匹配。 我们的算法结果的一个亮点是，一个人可以在$ \ tilde o（m+n^{3/2+ε}）中同时解决$ n $ -psp和ANSC的$ 2+ε$（以及任何常量的$ε> 0 $ $ 2+ε$）的$ 2+ε$（以及$ε$的添加误差）。对于$ n $ -PSP，我们的有条件下限意味着对于任何次级时间组合算法，该近似值几乎都是最佳的。我们进一步将这些算法扩展到$ n $ -PSP和ANSC，以获得包括接近线性时间算法在内的时间/准确性权衡。
We study the approximability of two related problems on graphs with $n$ nodes and $m$ edges: $n$-Pairs Shortest Paths ($n$-PSP), where the goal is to find a shortest path between $O(n)$ prespecified pairs, and All Node Shortest Cycles (ANSC), where the goal is to find the shortest cycle passing through each node. Approximate $n$-PSP has been previously studied, mostly in the context of distance oracles. We ask the question of whether approximate $n$-PSP can be solved faster than by using distance oracles or All Pair Shortest Paths (APSP). ANSC has also been studied previously, but only in terms of exact algorithms, rather than approximation. We provide a thorough study of the approximability of $n$-PSP and ANSC, providing a wide array of algorithms and conditional lower bounds that trade off between running time and approximation ratio. A highlight of our conditional lower bounds results is that for any integer $k\ge 1$, under the combinatorial $4k$-clique hypothesis, there is no combinatorial algorithm for unweighted undirected $n$-PSP with approximation ratio better than $1+1/k$ that runs in $O(m^{2-2/(k+1)}n^{1/(k+1)-ε})$ time. This nearly matches an upper bound implied by the result of Agarwal (2014). A highlight of our algorithmic results is that one can solve both $n$-PSP and ANSC in $\tilde O(m+ n^{3/2+ε})$ time with approximation factor $2+ε$ (and additive error that is function of $ε$), for any constant $ε>0$. For $n$-PSP, our conditional lower bounds imply that this approximation ratio is nearly optimal for any subquadratic-time combinatorial algorithm. We further extend these algorithms for $n$-PSP and ANSC to obtain a time/accuracy trade-off that includes near-linear time algorithms.
