7 citations · 9 across the 10 of their papers we have counts for
Showing cs.DSShow all
3 papers · 1 filter
cs.DS2019
Semidefinite Programming Relaxations of the Traveling Salesman Problem and Their Integrality Gaps
Samuel C. Gutekunst, David P. Williamson
The traveling salesman problem (TSP) is a fundamental problem in combinatorial optimization. Several semidefinite programming relaxations have been proposed recently that exploit a…
cs.DS2019
Characterizing the Integrality Gap of the Subtour LP for the Circulant Traveling Salesman Problem
Samuel C. Gutekunst, David P. Williamson
We consider the integrality gap of the subtour LP relaxation of the Traveling Salesman Problem restricted to circulant instances. De Klerk and Dobre conjectured that the value of t…
cs.DS2017
The Unbounded Integrality Gap of a Semidefinite Relaxation of the Traveling Salesman Problem
Samuel C. Gutekunst, David P. Williamson
We study a semidefinite programming relaxation of the traveling salesman problem introduced by de Klerk, Pasechnik, and Sotirov [8] and show that their relaxation has an unbounded…