On Lov[a-acute]sz--Schrijver Lift-and-Project Procedures on the Dantzig--Fulkerson--Johnson Relaxation of the TSP
On Lov[a-acute]sz--Schrijver Lift-and-Project Procedures on the Dantzig--Fulkerson--Johnson Relaxation of the TSP
复制标题
关于 TSP 的 Dantzig-Fulkerson-Johnson 松弛的 Lov[a-acute]sz--Schrijver Lift-and-Project 程序
DOI：
--
复制
发表时间：
2005
影响因子：
3.1
通讯作者：
Kevin K. H. Cheung
中科院分区：
文献类型：
--
作者：
Kevin K. H. Cheung
本文研究了旅行商问题（TSP）的Dantzig-Fulkerson-约翰逊线性松弛的Lovasz-Schrijver提升-投影方法N +$。一个长期存在的猜想指出，在度量成本的情况下，这种松弛的完整性差距是$frac43$。本文证明了2-匹配不等式相对于松弛的N+秩可以是任意高的，并得到了一个推论：即使对松弛应用N+次数，所得松弛的完整性间隙至少为frac 43。
We study the Lovasz--Schrijver lift-and-project procedure $N_+$ on the linear relaxation of the Dantzig--Fulkerson--Johnson formulation of the traveling salesman problem (TSP). A long standing conjecture states that the integrality gap of this relaxation is $frac43$ in the case of metric costs. In this paper, we show that the $N_+$-rank of 2-matching inequalities relative to this relaxation can be arbitrarily high and obtain as a corollary that even after applying $N_+$ to the relaxation a fixed number of times, the integrality gap of the resulting relaxation is at least $frac43$.