Back to search

Cornell University

Approximation Algorithms For Traveling Salesman Problems Based On Linear Programming Relaxations

Abstract

dc:description.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' 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.

Degree

thesis:*
Name thesis:degree_name
Ph. D., Computer Science
Level thesis:degree_level
Doctor of Philosophy
Discipline thesis:degree_discipline
Computer Science
Grantor
Cornell University
Year dc:date.issued
2012

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • An, Hyung Chan
Chair dc:contributor.chair
  • Shmoys, David B
Committee members dc:contributor.committeemember
  • Todd, Michael Jeremy
  • Huttenlocher, Daniel Peter
  • Kleinberg, Robert David

Subjects

dc:subject × 3

Rights

Language dc:language.iso
en_US

Identifiers

dc:identifier.*
Dc Identifier Bibid
7959757

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

An, Hyung Chan. Approximation Algorithms For Traveling Salesman Problems Based On Linear Programming Relaxations. Doctor of Philosophy thesis, Cornell University, 2012. https://hdl.handle.net/1813/31039