论文标题
TSP的半综合周期剪切实例的4/3-辅助算法
A 4/3-Approximation Algorithm for Half-Integral Cycle Cut Instances of the TSP
论文作者
论文摘要
对于旅行推销员问题（TSP）的一个长期猜想指出，标准线性编程放松的完整性差距最多为4/3。尽管做出了巨大的努力，但猜想仍然开放。 我们考虑了半综合案例，其中LP在$ \ {0、1/2、1 \} $中具有解决方案值。对于总体四分之二的猜想来说，这种实例已被认为是最困难的实例。 Karlin，Klein和Oveis Gharan的突破性结果表明，在半综合的情况下，整数差距最多为1.49993。这一结果导致数十年来总体猜想取得了首要的进展。同一位作者表明，在非半整合案例中，总差距最多为$ 1.5-10^{ - 36} $。对于半综合案例，当前最著名的比率为1.4983，这是Gupta等人的结果。 即使在半综合案例中，3/2绑定的改进也保持非常增量，我们扭转了问题，并寻找一类大型的半综合实例，我们可以证明4/3的猜想是正确的。 在LP解决方案的支撑图中，对半积分案例的临界集合的层次结构进行了先前的作品，其中某些集合对应于“循环切割”，而其他集合对应于“度削减”。我们表明，如果层次结构中的所有集合都对应于周期削减，那么我们可以找到一个旅行的分布，其预期成本最多是半积分LP解决方案的价值的4/3倍；来自分布的采样使我们有一个随机的4/3- approximation算法。我们注意到，完整性差距的已知不良病例的差距为4/3，并且具有半积分LP解决方案，其中层次结构中的所有临界紧密集均为循环削减；因此，我们的结果很紧。
A long-standing conjecture for the traveling salesman problem (TSP) states that the integrality gap of the standard linear programming relaxation of the TSP is at most 4/3. Despite significant efforts, the conjecture remains open. We consider the half-integral case, in which the LP has solution values in $\{0, 1/2, 1\}$. Such instances have been conjectured to be the most difficult instances for the overall four-thirds conjecture. Karlin, Klein, and Oveis Gharan, in a breakthrough result, were able to show that in the half-integral case, the integrality gap is at most 1.49993. This result led to the first significant progress on the overall conjecture in decades; the same authors showed the integrality gap is at most $1.5- 10^{-36}$ in the non-half-integral case. For the half-integral case, the current best-known ratio is 1.4983, a result by Gupta et al. With the improvements on the 3/2 bound remaining very incremental even in the half-integral case, we turn the question around and look for a large class of half-integral instances for which we can prove that the 4/3 conjecture is correct. The previous works on the half-integral case perform induction on a hierarchy of critical tight sets in the support graph of the LP solution, in which some of the sets correspond to "cycle cuts" and the others to "degree cuts". We show that if all the sets in the hierarchy correspond to cycle cuts, then we can find a distribution of tours whose expected cost is at most 4/3 times the value of the half-integral LP solution; sampling from the distribution gives us a randomized 4/3-approximation algorithm. We note that the known bad cases for the integrality gap have a gap of 4/3 and have a half-integral LP solution in which all the critical tight sets in the hierarchy are cycle cuts; thus our result is tight.
