Approximation Algorithms For Traveling Salesman Problems Based On Linear Programming Relaxations
Files
No Access Until
Permanent Link(s)
Collections
Other Titles
Author(s)
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.
Journal / Series
Volume & Issue
Description
Sponsorship
Date Issued
Publisher
Keywords
Location
Effective Date
Expiration Date
Sector
Employer
Union
Union Local
NAICS
Number of Workers
Committee Chair
Committee Co-Chair
Committee Member
Huttenlocher, Daniel Peter
Kleinberg, Robert David