dc.contributor.author Gutekunst, Samuel Christian dc.date.accessioned 2020-08-10T20:23:32Z dc.date.available 2020-08-10T20:23:32Z dc.date.issued 2020-05 dc.identifier.other Gutekunst_cornellgrad_0058F_12022 dc.identifier.other http://dissertations.umi.com/cornellgrad:12022 dc.identifier.uri https://hdl.handle.net/1813/70346 dc.description 169 pages 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 $c_{ij}$ 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}). dc.subject Approximation Algorithm dc.subject Circulant dc.subject Integrality Gap dc.subject Relaxation dc.subject Semidefinite Program dc.subject Traveling Salesman Problem dc.title Fantastic Relaxations of the TSP and How to Bound them: Relaxations of the Traveling Salesman Problem and their Integrality Gaps dc.type dissertation or thesis thesis.degree.discipline Operations Research and Information Engineering thesis.degree.grantor Cornell University thesis.degree.level Doctor of Philosophy thesis.degree.name Ph. D., Operations Research and Information Engineering dc.contributor.chair Williamson, David P. dc.contributor.committeeMember Meszaros, Karola dc.contributor.committeeMember Kleinberg, Robert dcterms.license https://hdl.handle.net/1813/59810 dc.identifier.doi https://doi.org/10.7298/f611-zh49
﻿