Semidefinite Programming Relaxations of the Traveling Salesman Problem and Their Integrality Gaps: The de Klerk–Sotirov SDP Has Integrality Gap at Least z for Every z ∈ ℕResearch Paper
The metric traveling salesman problem (TSP) asks for a shortest tour through cities whose pairwise costs are symmetric and satisfy the triangle inequality. The best-known guarantees for it come from relaxations: Christofides' -approximation is analysed against the subtour-elimination linear program (Held–Karp), and the integrality gap of that LP is…