论文标题
瓶颈不对称旅行者问题的近似算法
Approximation Algorithms for the Bottleneck Asymmetric Traveling Salesman Problem
论文作者
论文摘要
我们提出了第一个针对瓶颈不对称旅行者问题的非平地近似算法。鉴于N顶点之间的不对称度量成本，问题是要找到一个哈密顿周期，以最大程度地减少其瓶颈（或最大长度边缘）成本。我们通过将新颖的算法技术提供给快捷曲线欧拉电路的同时，在所需的快捷方式上，通过提供新颖的算法技术来实现O（log n / log n log n）近似性能保证。这使我们可以基于Asadpour，Goemans，MąDry，Oveis Gharan和Saberi的相关结果来获得此保证。此外，我们显示我们的技术在某些情况下如何产生更强的近似界限，例如Oveis Gharan和Saberi研究的有界定向属案例。我们还通过与问题的对称对应物进行比较，探讨了我们主要结果进一步改善的可能性。
We present the first nontrivial approximation algorithm for the bottleneck asymmetric traveling salesman problem. Given an asymmetric metric cost between n vertices, the problem is to find a Hamiltonian cycle that minimizes its bottleneck (or maximum-length edge) cost. We achieve an O(log n / log log n) approximation performance guarantee by giving a novel algorithmic technique to shortcut Eulerian circuits while bounding the lengths of the shortcuts needed. This allows us to build on a related result of Asadpour, Goemans, Mądry, Oveis Gharan, and Saberi to obtain this guarantee. Furthermore, we show how our technique yields stronger approximation bounds in some cases, such as the bounded orientable genus case studied by Oveis Gharan and Saberi. We also explore the possibility of further improvement upon our main result through a comparison to the symmetric counterpart of the problem.
