Please use this identifier to cite or link to this item:
http://hdl.handle.net/11375/9111
Full metadata record
DC Field | Value | Language |
---|---|---|
dc.contributor.advisor | Karakostas, George | en_US |
dc.contributor.author | Ma, Xiaoxi | en_US |
dc.date.accessioned | 2014-06-18T16:45:39Z | - |
dc.date.available | 2014-06-18T16:45:39Z | - |
dc.date.created | 2011-05-27 | en_US |
dc.date.issued | 2010 | en_US |
dc.identifier.other | opendissertations/4263 | en_US |
dc.identifier.other | 5282 | en_US |
dc.identifier.other | 2035678 | en_US |
dc.identifier.uri | http://hdl.handle.net/11375/9111 | - |
dc.description.abstract | <p>In this thesis we provide a Linear Programming (LP) formulation and a heuristic for the symmetric Traveling Salesman Problem (TSP) on certain complete graphs having the triangle inequality.</p> <p>TSP models cities and their pairwise connections as vertices and edges between them in a graph. The distances are represented by cost values on edges, and the goal is to find a minimum weight tour that visits every vertex exactly once. In symmetric cases all connections are undirected - both directions have the same cost. This problem is NP-Complete, so there is no polynomial time exact algorithm known for it.</p> <p>We present three major points in this thesis. Inspired by an LP formulation of perfect matching, we develop a relaxation for TSP, and prove that our relaxation is equivalent to the path form of the well-known Held-Karp formulation. Then, based on this relaxation we construct a heuristic, hoping it can approach a constant factor 4/3 of the optimal objective value given by the LP relaxation. At last, we adopt the matroid idea. It's already known that TSP can be modeled as minimum weight intersection of three matroids, but solving that is also NP-Complete. Vle present in this thesis the attempt to approach it using only two matroids, and analyze the difficulty.</p> | en_US |
dc.subject | Computing and Software | en_US |
dc.subject | Computer Engineering | en_US |
dc.subject | Computer Engineering | en_US |
dc.title | A Primal-Dual Heuristic for the Traveling Salesman Problem | en_US |
dc.type | thesis | en_US |
dc.contributor.department | Computing and Software | en_US |
dc.description.degree | Master of Science (MS) | en_US |
Appears in Collections: | Open Access Dissertations and Theses |
Files in This Item:
File | Size | Format | |
---|---|---|---|
fulltext.pdf | 2.47 MB | Adobe PDF | View/Open |
Items in MacSphere are protected by copyright, with all rights reserved, unless otherwise indicated.