<?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:35:44Z</responseDate><request verb="GetRecord" identifier="oai:ecommons.cornell.edu:1813/31039" metadataPrefix="dim">https://ecommons.cornell.edu/server/oai/request</request><GetRecord><record><header><identifier>oai:ecommons.cornell.edu:1813/31039</identifier><datestamp>2026-05-14T13:52:47Z</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" lang="en_US">An, Hyung Chan</dim:field>
   <dim:field mdschema="dc" element="contributor" qualifier="chair" lang="en_US">Shmoys, David B</dim:field>
   <dim:field mdschema="dc" element="contributor" qualifier="committeeMember" lang="en_US">Todd, Michael Jeremy</dim:field>
   <dim:field mdschema="dc" element="contributor" qualifier="committeeMember" lang="en_US">Huttenlocher, Daniel Peter</dim:field>
   <dim:field mdschema="dc" element="contributor" qualifier="committeeMember" lang="en_US">Kleinberg, Robert David</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="accessioned">2013-01-31T19:44:01Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="available">2017-12-20T07:00:33Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="issued" lang="en_US">2012-08-20</dim:field>
   <dim:field mdschema="dc" element="identifier" qualifier="uri">https://hdl.handle.net/1813/31039</dim:field>
   <dim:field mdschema="dc" element="identifier" qualifier="bibid">7959757</dim:field>
   <dim:field mdschema="dc" element="description" qualifier="abstract" lang="en_US">The traveling salesman problem (TSP) is the problem of finding a shortest Hamiltonian circuit or path in a given weighted graph. This problem has been studied in numerous variants, and linear programming has played an important role in the design of approximation algorithms for these problems. In this thesis, we study two versions of the traveling salesman problem and present approximation algorithms for them based on the Held-Karp relaxation. We first investigate the s-t path TSP. Hoogeveen showed that the natural variant of Christofides' algorithm is a 5/3-approximation algorithm for this problem; this asymptotically tight bound had remained the best approximation ratio known until now. We surpass this 20-year-old barrier by presenting a deterministic √ 1+ 5 -approximation 2 algorithm for the s-t path TSP for an arbi- trary metric. The techniques devised in this context can also be applied to other optimization problems including the prize-collecting s-t path problem and the unit-weight graphical metric s-t path TSP. The integrality gaps of the LP relaxations for all three problems are studied. Then we consider the bottleneck asymmetric TSP, where the objective is minimizing the bottleneck (or maximum-length) edge cost rather than the total edge cost. We present the first nontrivial approximation algorithm for this problem by giving a novel algorithmic technique to shortcut Eulerian circuits while bounding the lengths of the shortcuts needed. Building on this framework, and  the result of Asadpour, Goemans, Madry, Oveis Gharan, and Saberi, we achieve ֒ an O(log n/ log log n)-approximation algorithm. We also explore the possibility of improvement upon this result through a comparison to the symmetric counterpart of the problem.</dim:field>
   <dim:field mdschema="dc" element="language" qualifier="iso" lang="en_US">en_US</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en_US">approximation algorithms</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en_US">traveling salesman problem</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en_US">LP relaxations and rounding algorithms</dim:field>
   <dim:field mdschema="dc" element="title" lang="en_US">Approximation Algorithms For Traveling Salesman Problems Based On Linear Programming Relaxations</dim:field>
   <dim:field mdschema="dc" element="type" lang="en_US">dissertation or thesis</dim:field>
   <dim:field mdschema="dc" element="format" qualifier="mimetype">application/pdf</dim:field>
   <dim:field mdschema="thesis" element="degree" qualifier="discipline">Computer Science</dim:field>
   <dim:field mdschema="thesis" element="degree" qualifier="grantor" lang="en_US">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., Computer Science</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" lang="en_US">An, Hyung Chan</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="aac68313-c33d-49bd-892a-7df63ee835db">
	&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_US&lt;/Language>
   	&lt;Title>Approximation Algorithms For Traveling Salesman Problems Based On Linear Programming Relaxations&lt;/Title>
   	&lt;PublishedIn>
    	&lt;Publication>
      	&lt;/Publication>
   	&lt;/PublishedIn>
   	&lt;PublicationDate>2012-08-20&lt;/PublicationDate>
   	&lt;Authors>
      	&lt;Author>
        	&lt;DisplayName>An, Hyung Chan&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 algorithms&lt;/Keyword>
    &lt;Keyword>traveling salesman problem&lt;/Keyword>
    &lt;Keyword>LP relaxations and rounding algorithms&lt;/Keyword>
   	&lt;Abstract>The traveling salesman problem (TSP) is the problem of finding a shortest Hamiltonian circuit or path in a given weighted graph. This problem has been studied in numerous variants, and linear programming has played an important role in the design of approximation algorithms for these problems. In this thesis, we study two versions of the traveling salesman problem and present approximation algorithms for them based on the Held-Karp relaxation. We first investigate the s-t path TSP. Hoogeveen showed that the natural variant of Christofides&amp;apos; algorithm is a 5/3-approximation algorithm for this problem; this asymptotically tight bound had remained the best approximation ratio known until now. We surpass this 20-year-old barrier by presenting a deterministic √ 1+ 5 -approximation 2 algorithm for the s-t path TSP for an arbi- trary metric. The techniques devised in this context can also be applied to other optimization problems including the prize-collecting s-t path problem and the unit-weight graphical metric s-t path TSP. The integrality gaps of the LP relaxations for all three problems are studied. Then we consider the bottleneck asymmetric TSP, where the objective is minimizing the bottleneck (or maximum-length) edge cost rather than the total edge cost. We present the first nontrivial approximation algorithm for this problem by giving a novel algorithmic technique to shortcut Eulerian circuits while bounding the lengths of the shortcuts needed. Building on this framework, and  the result of Asadpour, Goemans, Madry, Oveis Gharan, and Saberi, we achieve ֒ an O(log n/ log log n)-approximation algorithm. We also explore the possibility of improvement upon this result through a comparison to the symmetric counterpart of the problem.&lt;/Abstract>
	&lt;Access xmlns="http://purl.org/coar/access_right" 
    >
    &lt;/Access>
&lt;/Publication>
</dim:field>
</dim:dim>
</metadata></record></GetRecord></OAI-PMH>