Fantastic Relaxations of the TSP and How to Bound them: Relaxations of the Traveling Salesman Problem and their Integrality Gaps

Other Titles


The Traveling Salesman Problem (TSP) is a fundamental problem in combinatorial optimization, combinatorics, and theoretical computer science and is a canonical NP-hard problem. Given a set of n vertices and pairwise costs cij of traveling between vertices i and j, the TSP asks for a minimum-cost tour visiting each of the vertices exactly once (i.e., a minimum-cost Hamiltonian cycle). Despite the problem's ubiquity, the state-of-the-art TSP approximation algorithm dates back more than 40 years. Its performance guarantee can be derived using a linear program \emph{relaxation} that is over 50 years old, but the best-known analysis of this linear program's \emph{integrality gap} (which dictates its use in proving approximation guarantees) has not been improved in nearly 40 years of active research. This thesis contributes to two main avenues of TSP research towards breaking these bottlenecks, both of which involve analyzing TSP relaxations. We first consider relaxations of the TSP that are based on \emph{semidefinite programs} (SDPs). Recently, many such relaxations have been proposed as avenues towards better approximation algorithms. These SDPs exploit a breadth of mathematical structures and have shown considerable promise in small numerical experiments, but little has been known about their general performance. Our first main results fill this void: we provide the first theoretical analysis of the integrality gap of every major SDP relaxation of the TSP. Specifically, with standard costs that are symmetric and obey the triangle inequality, we show that every major SDP relaxation of the TSP has an unbounded integrality gap. To do so, we develop a systematic methodology that exploits symmetry. Our methodology allows us to analyze, e.g., SDPs from \cite{ Ans00, Cvet99, Klerk12, Klerk08, Klerk12b, Had92, Povh09, Zhao98} (some of these SDPs are now known to find equivalent optimal values), and extends to SDP relaxations of the Quadratic Assignment Problem and the k-cycle cover problem. Our results contrast starkly with analysis of the 50-year-old linear program relaxation, whose integrality gap is at most \f32. In the second part of this thesis, we turn to the prototypical linear program relaxation of the TSP, the subtour elimination LP. We analyze this relaxation on an important but non-metric set of instances: \emph{circulant TSP} instances. Circulant TSP instances are particularly compelling because circulant instances impose enough structure to make some -- but not all -- NP-hard problems easy. De Klerk and Dobre \cite{Klerk11} conjectured that, when instances are circulant, the subtour elimination LP is equivalent to a combinatorial lower bound of Van der Veen, Van Dal, and Sierksma \cite{VDV91}. We resolve this conjecture in the affirmative, exploiting symmetry to find a readily-computable, analytic solution to the subtour elimination LP on circulant instances. Using this same symmetry, we show that the integrality gap of the subtour elimination LP on circulant instances is exactly 2; we show that this gap remains unchanged even when the crown, ladder, and chain inequalities are added (see \cite{Boyd91, Nad92, Pad80}).

Journal / Series

Volume & Issue


169 pages


Date Issued




Approximation Algorithm; Circulant; Integrality Gap; Relaxation; Semidefinite Program; Traveling Salesman Problem


Effective Date

Expiration Date




Union Local


Number of Workers

Committee Chair

Williamson, David P.

Committee Co-Chair

Committee Member

Meszaros, Karola
Kleinberg, Robert

Degree Discipline

Operations Research and Information Engineering

Degree Name

Ph. D., Operations Research and Information Engineering

Degree Level

Doctor of Philosophy

Related Version

Related DOI

Related To

Related Part

Based on Related Item

Has Other Format(s)

Part of Related Item

Related To

Related Publication(s)

Link(s) to Related Publication(s)


Link(s) to Reference(s)

Previously Published As

Government Document




Other Identifiers


Rights URI


dissertation or thesis

Accessibility Feature

Accessibility Hazard

Accessibility Summary

Link(s) to Catalog Record