A constant-factor approximation algorithm for the asymmetric traveling salesman problem
A constant-factor approximation algorithm for the asymmetric traveling salesman problem
复制标题
非对称旅行商问题的常因子逼近算法
DOI：
10.1145/3188745.3188824
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Svensson O
中科院分区：
文献类型：
--
作者：
Svensson O
针对不对称旅行商问题，给出了一种常因子逼近算法。对标准LP松弛的近似保证进行了分析，从而证实了该松弛的常积分间隙的推测。我们的方法的主要思想是减少Subtour Partition Cover，这是一个更容易的问题，通过显着放宽一般连通性要求到局部连通性条件。我们首先证明了任何Subtour Partition Cover算法都可以转化为ATSP算法，而在性能保证中只损失一个很小的常数因子。接下来，我们提出了从一般ATSP实例到结构化实例的约简，然后在此基础上我们求解Subtour Partition Cover，得到我们的ATSP常因子近似算法。
We give a constant-factor approximation algorithm for the asymmetric traveling salesman problem (ATSP). Our approximation guarantee is analyzed with respect to the standard LP relaxation, and thus our result confirms the conjectured constant integrality gap of that relaxation.The main idea of our approach is a reduction to Subtour Partition Cover, an easier problem obtained by significantly relaxing the general connectivity requirements into local connectivity conditions. We first show that any algorithm for Subtour Partition Cover can be turned into an algorithm for ATSP while only losing a small constant factor in the performance guarantee. Next, we present a reduction from general ATSP instances to structured instances, on which we then solve Subtour Partition Cover, yielding our constant-factor approximation algorithm for ATSP.
登录
查看更多内容
DOI：
--
发表时间：
2010
期刊：
International Workshop and International Workshop on Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
影响因子：
--
作者：
Hyung;Robert D. Kleinberg;D. Shmoys
通讯作者：
D. Shmoys
非对称旅行商路径 LP 具有恒定的完整性比
影响因子：
2.7
作者：
Anna Köhne;Vera Traub;J. Vygen
通讯作者：
J. Vygen
具有两个边权重的 ATSP 的常数因子近似
影响因子：
2.7
作者：
O. Svensson;Jakub Tarnawski;László A. Végh
通讯作者：
László A. Végh
有效减阻流、光谱稀疏树和不对称 TSP
DOI：
--
发表时间：
2014
期刊：
IEEE Annual Symposium on Foundations of Computer Science
影响因子：
--
作者：
Nima Anari;S. Gharan
通讯作者：
S. Gharan
改进了有向图中旅行推销员游览和路径的近似比
DOI：
--
发表时间：
2007
期刊：
International Workshop and International Workshop on Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
影响因子：
--
作者：
U. Feige;Mohit Singh
通讯作者：
Mohit Singh