Open Collections

Semidefinite Programming Relaxations of the Traveling Salesman Problem

Banff International Research Station for Mathematical Innovation and Discovery

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.

Mathematics; Computer science; Operations research, mathematical programming; Theoretical computer science

video/mp4

Author affiliation: Cornell University

2020-12-06

Attribution-NonCommercial-NoDerivatives 4.0 International

http://hdl.handle.net/2429/76668

Unreviewed

http://creativecommons.org/licenses/by-nc-nd/4.0/