2-Matchings, the Traveling Salesman Problem, and the Subtour LP: A Proof of the Boyd-Carr Conjecture
2-Matchings, the Traveling Salesman Problem, and the Subtour LP: A Proof of the Boyd-Carr Conjecture
复制标题
2-匹配、旅行商问题和 Subtour LP：博伊德卡尔猜想的证明
DOI：
10.1287/moor.2013.0608
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
A. V. Zuylen
中科院分区：
文献类型：
--
作者：
Frans Schalekamp;David P. Williamson;A. V. Zuylen
确定旅行商问题的子游线性规划（LP）松弛的精确积分间隙是一个重要的开放性问题，在一般的服从三角形不等式的对称代价情况下，30年来取得的进展很少。Boyd和Carr [Boyd S， Carr R（2011）利用某些半整数子游顶点寻找低成本TSP和2-匹配解。]离散优化。8:525-539。2011年6月27日访问的先前版本http://www.site.uottawa.ca/~sylvia/recentpapers/halftri.pdf.]观察到，我们甚至不知道最优2匹配与子tour LP之比的最坏情况上界；他们推测比值不超过10/9。本文证明了Boyd-Carr猜想。在分数阶2匹配的支持没有切边的情况下，我们可以进一步证明最优2匹配的代价最多是分数阶2匹配代价的10/9倍。
Determining the precise integrality gap for the subtour linear programming (LP) relaxation of the traveling salesman problem is a significant open question, with little progress made in thirty years in the general case of symmetric costs that obey triangle inequality. Boyd and Carr [Boyd S, Carr R (2011) Finding low cost TSP and 2-matching solutions using certain half-integer subtour vertices. Discrete Optim. 8:525–539. Prior version accessed June 27, 2011, http://www.site.uottawa.ca/~sylvia/recentpapers/halftri.pdf.] observe that we do not even know the worst-case upper bound on the ratio of the optimal 2-matching to the subtour LP; they conjecture the ratio is at most 10/9. In this paper, we prove the Boyd-Carr conjecture. In the case that the support of a fractional 2-matching has no cut edge, we can further prove that an optimal 2-matching has cost at most 10/9 times the cost of the fractional 2-matching.