Journal
SIAM JOURNAL ON OPTIMIZATION
Volume 28, Issue 3, Pages 2073-2096Publisher
SIAM PUBLICATIONS
DOI: 10.1137/17M1154722
Keywords
traveling salesman problem; approximation algorithms; semidefinite programming
Categories
Funding
- NSF [CCF-1552831]
- National Science Foundation [DGE-1650441]
Ask authors/readers for more resources
We study a semidefinite programming relaxation of the traveling salesman problem introduced by de Klerk, Pasechnik, and Sotirov [SIAM J. Optim., 19 (2008), pp. 1559-1573] and show that their relaxation has an unbounded integrality gap. In particular, we give a family of instances 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 for a related linear program, which we do analytically. The solutions we find imply the unbounded integrality gap. Further, these solutions imply several corollaries that help us better understand the semidefinite program and its relationship to other TSP relaxations. Using the same technique, we show that a more general semidefinite program introduced by de Klerk, de Oliveira Filho, and Pasechnik [Handbook on Semidefinite, Conic and Polynomial Optimization, Springer, New York, 2012, pp. 171-199.] for the k-cycle cover problem also has an unbounded integrality gap.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available