Approximation Algorithms for the Bottleneck Asymmetric Traveling Salesman Problem
Approximation Algorithms for the Bottleneck Asymmetric Traveling Salesman Problem
复制标题
瓶颈非对称旅行商问题的近似算法
DOI：
--
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
D. Shmoys
中科院分区：
文献类型：
--
作者：
Hyung;Robert D. Kleinberg;D. Shmoys
给出了求解瓶颈非对称旅行商问题的第一非平凡近似算法。给定n个顶点之间的非对称度量成本，问题是找到一个最小化其瓶颈（或最大长度边）成本的Hamilton圈。我们实现了O（log n/ log log n）的近似性能保证，给出了一种新的算法技术，以缩短欧拉电路，同时限制所需的捷径的长度。这使我们能够建立在Asadpour，Goemans，Mackdry，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.