An improved approximation algorithm for TSP in the half integral case
An improved approximation algorithm for TSP in the half integral case
复制标题
DOI：
10.1145/3357713.3384273
复制
发表时间：
2019-08
期刊：
影响因子：
--
通讯作者：
Anna R. Karlin;N. Klein;S. Gharan
中科院分区：
文献类型：
--
作者：
Anna R. Karlin;N. Klein;S. Gharan
我们设计了一个1.49993-近似算法的度量旅行推销员问题（TSP）的例子，其中的最优解的子环线性规划松弛是半整数。这些情况在过去的十年中受到了极大的关注，因为Schalekamp，威廉姆森和货车Zuylen的猜想指出，半积分LP解决方案具有最大的完整性差距超过所有分数的解决方案。因此，如果Schalekamp等人的猜想成立，我们的结果表明，子环多胞形的完整性间隙是有界的，远离3/2。
We design a 1.49993-approximation algorithm for the metric traveling salesperson problem (TSP) for instances in which an optimal solution to the subtour linear programming relaxation is half-integral. These instances received significant attention over the last decade due to a conjecture of Schalekamp, Williamson and van Zuylen stating that half-integral LP solutions have the largest integrality gap over all fractional solutions. So, if the conjecture of Schalekamp et al. holds true, our result shows that the integrality gap of the subtour polytope is bounded away from 3/2.