<?xml version='1.0' encoding='UTF-8'?><?xml-stylesheet href='static/style.xsl' type='text/xsl'?><OAI-PMH xmlns="http://www.openarchives.org/OAI/2.0/" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://www.openarchives.org/OAI/2.0/ http://www.openarchives.org/OAI/2.0/OAI-PMH.xsd"><responseDate>2026-11-22T09:30:06Z</responseDate><request verb="GetRecord" identifier="oai:ecommons.cornell.edu:1813/70346" metadataPrefix="dim">https://ecommons.cornell.edu/server/oai/request</request><GetRecord><record><header><identifier>oai:ecommons.cornell.edu:1813/70346</identifier><datestamp>2026-05-15T19:49:45Z</datestamp><setSpec>com_1813_35</setSpec><setSpec>col_1813_47</setSpec></header><metadata><dim:dim xmlns:dim="http://www.dspace.org/xmlns/dspace/dim" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xmlns:doc="http://www.lyncode.com/xoai" xsi:schemaLocation="http://www.dspace.org/xmlns/dspace/dim http://www.dspace.org/schema/dim.xsd">
   <dim:field mdschema="dc" element="contributor" qualifier="author">Gutekunst, Samuel Christian</dim:field>
   <dim:field mdschema="dc" element="contributor" qualifier="chair">Williamson, David P.</dim:field>
   <dim:field mdschema="dc" element="contributor" qualifier="committeeMember">Meszaros, Karola</dim:field>
   <dim:field mdschema="dc" element="contributor" qualifier="committeeMember">Kleinberg, Robert</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="accessioned">2020-08-10T20:23:32Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="available">2020-08-10T20:23:32Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="issued">2020-05</dim:field>
   <dim:field mdschema="dc" element="identifier" qualifier="other">ProQuest Submission ID: 12022</dim:field>
   <dim:field mdschema="dc" element="identifier" qualifier="other">ProQuest Publication ID: 27993667</dim:field>
   <dim:field mdschema="dc" element="identifier" qualifier="uri">https://hdl.handle.net/1813/70346</dim:field>
   <dim:field mdschema="dc" element="identifier" qualifier="doi">https://doi.org/10.7298/f611-zh49</dim:field>
   <dim:field mdschema="dc" element="identifier" qualifier="bibid">13254323</dim:field>
   <dim:field mdschema="dc" element="description">169 pages</dim:field>
   <dim:field mdschema="dc" element="description" qualifier="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}).</dim:field>
   <dim:field mdschema="dc" element="language" qualifier="iso">en</dim:field>
   <dim:field mdschema="dc" element="subject">Approximation Algorithm</dim:field>
   <dim:field mdschema="dc" element="subject">Circulant</dim:field>
   <dim:field mdschema="dc" element="subject">Integrality Gap</dim:field>
   <dim:field mdschema="dc" element="subject">Relaxation</dim:field>
   <dim:field mdschema="dc" element="subject">Semidefinite Program</dim:field>
   <dim:field mdschema="dc" element="subject">Traveling Salesman Problem</dim:field>
   <dim:field mdschema="dc" element="title">Fantastic Relaxations of the TSP and How to Bound them: Relaxations of the Traveling Salesman Problem and their Integrality Gaps</dim:field>
   <dim:field mdschema="dc" element="type">dissertation or thesis</dim:field>
   <dim:field mdschema="dc" element="relation" qualifier="localuri">https://catalog.library.cornell.edu/catalog/13254323</dim:field>
   <dim:field mdschema="dc" element="format" qualifier="mimetype">application/pdf</dim:field>
   <dim:field mdschema="thesis" element="degree" qualifier="discipline">Operations Research and Information Engineering</dim:field>
   <dim:field mdschema="thesis" element="degree" qualifier="grantor">Cornell University</dim:field>
   <dim:field mdschema="thesis" element="degree" qualifier="level">Doctor of Philosophy</dim:field>
   <dim:field mdschema="thesis" element="degree" qualifier="name">Ph. D., Operations Research and Information Engineering</dim:field>
   <dim:field mdschema="dcterms" element="license">https://hdl.handle.net/1813/59810</dim:field>
   <dim:field mdschema="dspace" element="entity" qualifier="type">Publication</dim:field>
   <dim:field mdschema="cris" element="virtual" qualifier="collection" authority="https://cornell-ecommons.eks.prod.4science.cloud/handle/1813/47" confidence="600">Cornell Theses and Dissertations</dim:field>
   <dim:field mdschema="cris" element="virtual" qualifier="author">Gutekunst, Samuel Christian</dim:field>
   <dim:field mdschema="cris" element="virtualsource" qualifier="collection">5893a6ea-7af3-41d7-abc6-04bcd26ab5df</dim:field>
   <dim:field mdschema="others" element="access-status">open.access</dim:field>
   <dim:field mdschema="others" element="access-status">open.access</dim:field>
   <dim:field mdschema="cerif" element="openaire" authority="" confidence="-1">&lt;Publication xmlns="https://www.openaire.eu/cerif-profile/1.1/" id="2b7621f8-f944-4b59-81a7-404eccb54adc">
	&lt;Type xmlns="https://www.openaire.eu/cerif-profile/vocab/COAR_Publication_Types">http://purl.org/coar/resource_type/c_1843&lt;/Type>
	&lt;Language>en&lt;/Language>
   	&lt;Title>Fantastic Relaxations of the TSP and How to Bound them: Relaxations of the Traveling Salesman Problem and their Integrality Gaps&lt;/Title>
   	&lt;PublishedIn>
    	&lt;Publication>
      	&lt;/Publication>
   	&lt;/PublishedIn>
   	&lt;PublicationDate>2020-05&lt;/PublicationDate>
   	&lt;DOI>https://doi.org/10.7298/f611-zh49&lt;/DOI>
   	&lt;Authors>
      	&lt;Author>
        	&lt;DisplayName>Gutekunst, Samuel Christian&lt;/DisplayName>
         	&lt;Affiliation>
         		&lt;OrgUnit>
         		&lt;/OrgUnit>
         	&lt;/Affiliation>
      	&lt;/Author>
	&lt;/Authors>
   	&lt;Editors>
	&lt;/Editors>
    &lt;Publishers>
        &lt;Publisher>
            &lt;OrgUnit />
        &lt;/Publisher>
    &lt;/Publishers>
    &lt;Keyword>Approximation Algorithm&lt;/Keyword>
    &lt;Keyword>Circulant&lt;/Keyword>
    &lt;Keyword>Integrality Gap&lt;/Keyword>
    &lt;Keyword>Relaxation&lt;/Keyword>
    &lt;Keyword>Semidefinite Program&lt;/Keyword>
    &lt;Keyword>Traveling Salesman Problem&lt;/Keyword>
   	&lt;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&amp;apos;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&amp;apos;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}).&lt;/Abstract>
	&lt;Access xmlns="http://purl.org/coar/access_right" 
    >
    &lt;/Access>
&lt;/Publication>
</dim:field>
</dim:dim>
</metadata></record></GetRecord></OAI-PMH>