BIRS Workshop Lecture Videos

Banff International Research Station Logo

BIRS Workshop Lecture Videos

Semidefinite Programming Relaxations of the Traveling Salesman Problem Gutekunst, Sam


In this talk, we analyze a semidefinite programming relaxation of the traveling salesman problem due to de Klerk, Pasechnik, and Sotirov. Our main result is that their relaxation has an unbounded integrality gap. In particular, we give a family of instances such that the gap increases linearly with the number of cities on the tour. To obtain this result, we search for feasible solutions within a highly structured class of cost matrices; the problem of finding such solutions reduces to finding feasible solutions for a related linear program, which we do analytically. The solutions we find imply the unbounded integrality gap. Further, they imply several corollaries that help us better understand the semidefinite program and its relationship to other linear and semidefinite relaxations of the traveling salesman problem. Using the same technique, we show that a more general semidefinite program introduced by de Klerk, de Oliveira Filho, and Pasechnik for the k-cycle cover problem also has an unbounded integrality gap.

Item Media

Item Citations and Data


Attribution-NonCommercial-NoDerivatives 4.0 International