The traveling salesman problem and its applications
THE TRAVELING SALESMAN PROBLEM AND ITS APPLICATIONS
submitted by Ming-Ki HUI
for the degree of Master of Philosophy at The University of Hong Kong
in August 2002
Given a complete graph G with a weight on each edge, the traveling salesman problem (TSP) is to find a shortest cycle that traverses every node of G exactly once. This problem has numerous important applications in the real world, so it has attracted tremendous research efforts from various fields and hence served as a testing ground for many algorithmic ideas. Since it is N Phard in general, there is no polynomial-time algorithm for solving it exactly unless P = N P. Therefore, in view of the computational difficulty, it is well motivated to find a near-optimal solution to this problem instead. A more recent result reveals that the TSP problem cannot even be approximated within any constant factor, thus it will be natural and interesting to investigate the
problem in some special cases.
The present thesis is devoted to various special TSP problems and applications. The TSP problem is called Metric if the weights satisfy the triangle inequality. A 3j2-approximation algorithm is given for the Metric TSP problem, which heavily relies on the weighted matching algorithm to achieve the best existing approximation ratio.
The Euclidean TSP is the special case in which nodes lie in the twodimensional plane, and the weight on each edge is defined as the Euclidean distance between the two ends of the edge. The planar graph TSP is the special case in which nodes lie in a planar graph, and the weight between two nodes is given by the length of their shortest path. Polynomial time approximation schemes (PTAS) are presented for these two special cases. The basic idea underlying these two algorithms is to recursively decompose the plane into certain smaller pieces and then employ the dynamic-programming technique.
Given a finite alphabet :E and a set of n strings 31,32, ... ,3n over :E, the Shortest Superstring Problem aims to find a shortest string s over :E that contains each 3i as a substring. This problem arises in the area of computatioal biology and can be modelled as a special TSP problem. An approximation algorithm is given for solving the problem with a performance guarantee of 3.
School:The University of Hong Kong
School Location:China - Hong Kong SAR
Source Type:Master's Thesis
Keywords:traveling salesman problem combinatorial optimization
Date of Publication:01/01/2003