Finding low cost TSP and 2-matching solutions using certain half-integer subtour vertices
Finding low cost TSP and 2-matching solutions using certain half-integer subtour vertices
复制标题
使用某些半整数子旅行顶点寻找低成本 TSP 和 2 匹配解
DOI：
10.1016/j.disopt.2011.05.002
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
R. Carr
中科院分区：
文献类型：
--
作者：
Sylvia C. Boyd;R. Carr
考虑定义在完全图上的旅行商问题（TSP），其中边费用满足三角不等式。让TOUR表示TSP的最优解值。TSP的两个著名的松弛是子环消除问题和2-匹配问题。如果我们让SUBT和2 M代表这两个松弛的最佳解值，则推测TOUR/SUBT ≤4/3，2 M/SUBT ≤10/9。本文利用子环消去问题的1/2-整数解的结构来获得低成本的TSP和2-匹配解。特别是，我们表明，成本函数的最佳子巡回消除解决方案发现福尔斯落入我们的类，上述两个命题是真的。我们的证明是建设性的，可以在多项式时间内实现，因此，对于这样的成本函数，提供了一个4/3（或更好）的近似算法的TSP。
Consider the traveling salesman problem (TSP) defined on the complete graph, where the edge costs satisfy the triangle inequality. Let TOUR denote the optimal solution value for the TSP. Two well-known relaxations of the TSP are the subtour elimination problem and the 2-matching problem. If we let SUBT and 2M represent the optimal solution values for these two relaxations, then it has been conjectured that TOUR/SUBT ≤4/3, and that 2M/SUBT ≤10/9. In this paper, we exploit the structure of certain 1/2-integer solutions for the subtour elimination problem in order to obtain low cost TSP and 2-matching solutions. In particular, we show that for cost functions for which the optimal subtour elimination solution found falls into our classes, the above two conjectures are true. Our proofs are constructive and could be implemented in polynomial time, and thus, for such cost functions, provide a 4/3 (or better) approximation algorithm for the TSP.