Semidefinite Programming Relaxations of the Traveling Salesman Problem and Their Integrality Gaps
Semidefinite Programming Relaxations of the Traveling Salesman Problem and Their Integrality Gaps
The traveling salesman problem (TSP) is a fundamental problem in combinatorial optimization. Several semidefinite programming relaxations have been proposed recently that exploit a variety of mathematical structures including, for example, algebraic connectivity, permutation matrices, and association schemes. The main results of this paper are twofold. First, de Klerk and Sotirov …