Please use this identifier to cite or link to this item:
http://hdl.handle.net/11375/9111
Title: | A Primal-Dual Heuristic for the Traveling Salesman Problem |
Authors: | Ma, Xiaoxi |
Advisor: | Karakostas, George |
Department: | Computing and Software |
Keywords: | Computing and Software;Computer Engineering;Computer Engineering |
Publication Date: | 2010 |
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> |
URI: | http://hdl.handle.net/11375/9111 |
Identifier: | opendissertations/4263 5282 2035678 |
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.