Back to search

Cornell University

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

Abstract

dc:description.abstract

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 $\f{3}{2}$. 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}).

Degree

thesis:*
Name thesis:degree_name
Ph. D., Operations Research and Information Engineering
Level thesis:degree_level
Doctor of Philosophy
Discipline thesis:degree_discipline
Operations Research and Information Engineering
Grantor
Cornell University
Year dc:date.issued
2020

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Gutekunst, Samuel Christian
Chair dc:contributor.chair
  • Williamson, David P.
Committee members dc:contributor.committeemember
  • Meszaros, Karola
  • Kleinberg, Robert

Subjects

dc:subject × 6

Rights

Language dc:language.iso
en

Identifiers

dc:identifier.*
Dc Identifier Bibid
13254323
Dc Identifier Other
ProQuest Submission ID: 12022
ProQuest Publication ID: 27993667

Chain of custody

source
Harvested from
Cornell University
Base URL
ecommons.cornell.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Gutekunst, Samuel Christian. Fantastic Relaxations of the TSP and How to Bound them: Relaxations of the Traveling Salesman Problem and their Integrality Gaps. Doctor of Philosophy thesis, Cornell University, 2020. https://hdl.handle.net/1813/70346