Towards improving Christofides algorithm for half-integer TSP
Towards improving Christofides algorithm for half-integer TSP
复制标题
改进半整数 TSP 的 Christofides 算法
DOI：
10.4230/lipics.esa.2019.56
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Alantha Newman
中科院分区：
文献类型：
--
作者：
A. Haddadan;Alantha Newman
我们研究了子圈线性规划松弛的目标函数被半循环点$x_e最小化的旅行商问题(TSP)，其中半边形成2因子，1边形成完美匹配。这些点通常足以解决半整数TSP问题，并已被猜想为证明了次巡回松弛的最大完整性间隙。
对于半循环点，最著名的逼近保证是$3/2$，这是由于Christofides著名的算法。证明了子圈松弛的完整性差为$\α$，等价于证明了$\αx$可以表示为环游的凸组合，其中$x$是该松弛的任意可行解。为了击败Christofides界，我们的目标是证明$(2-\epsilon)x$可以写成某个正常数$\epsilon$的巡回的凸组合。当$x_e=1$时，设$y_e=2-\epsilon$；当$x_e=1/2$时，设$y_e=3/4$。作为实现这一目标的第一步，我们的主要结果是证明了$y$可以写成巡游的凸组合。换句话说，我们证明了我们可以在1-边上节省，这有几个应用。其中，给出了最近研究的一致覆盖问题的另一种算法。我们的主要新技术是在适当的3边切割上粘合旅游，这些切割相对于$x$是紧的，从而将问题减少到基本情况下，在这种切割不发生的情况下。
We study the traveling salesman problem (TSP) in the case when the objective function of the subtour linear programming relaxation is minimized by a half-cycle point: $x_e \in \{ 0 ,1/2 , 1 \}$ where the half-edges form a 2-factor and the 1-edges form a perfect matching. Such points are sufficient to resolve half-integer TSP in general and they have been conjectured to demonstrate the largest integrality gap for the subtour relaxation.
For half-cycle points, the best-known approximation guarantee is $3/2$ due to Christofides famous algorithm. Proving an integrality gap of $\alpha$ for the subtour relaxation is equivalent to showing that $\alpha x$ can be written as a convex combination of tours, where $x$ is any feasible solution for this relaxation. To beat Christofides bound, our goal is to show that $(2-\epsilon)x$ can be written as a convex combination of tours for some positive constant $\epsilon$. Let $y_e = 2-\epsilon$ when $x_e=1$ and $y_e= 3/4$ when $x_e = 1/2$. As a first step towards this goal, our main result is to show that $y$ can be written as a convex combination of tours. In other words, we show that we can save on 1-edges, which has several applications. Among them, it gives an alternative algorithm for the recently studied uniform cover problem. Our main new technique is a procedure to glue tours over proper 3-edge cuts that are tight with respect to $x$ , thus reducing the problem to a base case in which such cuts do not occur.