We study a semidefinite programming relaxation of the traveling salesmanproblem introduced by de Klerk, Pasechnik, and Sotirov [8] and show that theirrelaxation has an unbounded integrality gap. In particular, we give a family ofinstances such that the gap increases linearly with $n$. To obtain this result,we search for feasible solutions within a highly structured class of matrices;the problem of finding such solutions reduces to finding feasible solutions fora related linear program, which we do analytically. The solutions we find implythe unbounded integrality gap. Further, they imply several corollaries thathelp us better understand the semidefinite program and its relationship toother TSP relaxations. Using the same technique, we show that a more generalsemidefinite program introduced by de Klerk, de Oliveira Filho, and Pasechnik[7] for the $k$-cycle cover problem also has an unbounded integrality gap.
展开▼
机译：我们研究了de Klerk，Pasechnik和Sotirov [8]引入的旅行商问题的半定程序松弛，并表明它们的松弛具有无限的完整性差距。特别是，我们给出了一系列实例，使得缺口随着$ n $线性增加。为了获得此结果，我们在高度结构化的矩阵类别中搜索可行的解；找到此类解的问题减少到为相关线性程序找到可行解的过程，我们对此进行了分析。我们发现的解决方案意味着无限的完整性差距。此外，它们暗示了一些推论，它们可以帮助我们更好地理解半定程序及其与其他TSP松弛的关系。使用相同的技术，我们证明了de Klerk，de Oliveira Filho和Pasechnik [7]针对$ k $循环覆盖问题引入的更一般的半确定性程序也具有无限的完整性差距。
展开▼
