Approximation Algorithms For Traveling Salesman Problems Based On Linear Programming Relaxations
| dc.contributor.author | An, Hyung Chan | en_US |
| dc.contributor.chair | Shmoys, David B | en_US |
| dc.contributor.committeeMember | Todd, Michael Jeremy | en_US |
| dc.contributor.committeeMember | Huttenlocher, Daniel Peter | en_US |
| dc.contributor.committeeMember | Kleinberg, Robert David | en_US |
| dc.date.accessioned | 2013-01-31T19:44:01Z | |
| dc.date.available | 2017-12-20T07:00:33Z | |
| dc.date.issued | 2012-08-20 | en_US |
| 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. | en_US |
| dc.identifier.other | bibid: 7959757 | |
| dc.identifier.uri | https://hdl.handle.net/1813/31039 | |
| dc.language.iso | en_US | en_US |
| dc.subject | approximation algorithms | en_US |
| dc.subject | traveling salesman problem | en_US |
| dc.subject | LP relaxations and rounding algorithms | en_US |
| dc.title | Approximation Algorithms For Traveling Salesman Problems Based On Linear Programming Relaxations | en_US |
| dc.type | dissertation or thesis | en_US |
| thesis.degree.discipline | Computer Science | |
| thesis.degree.grantor | Cornell University | en_US |
| thesis.degree.level | Doctor of Philosophy | |
| thesis.degree.name | Ph. D., Computer Science |
Files
Original bundle
1 - 1 of 1