A Patching Algorithm for the Nonsymmetric Traveling-Salesman Problem
Richard M. Karp · SIAM Journal on Computing · 1979
We present an algorithm for the approximate solution of the nonsymmetric n-city traveling-salesman problem. An instance of this problem is specified by a $n \times n$ distance matrix $D = (d_{ij} )$. The algorithm first solves the assignment problem for the matrix D, and then patches the cycles of the optimum assignment together to form a tour. The execution time of the algorithm is comparable to the time required to solve an $n \times n$ assignment problem. If the distances $d_{ij} $ are drawn independently from a uniform distribution then, with probability tending to 1, the ratio of the cost of the tour produced by the algorithm to the cost of an optimum tour is $ < 1 + \varepsilon (n)$, where $\varepsilon (n)$ goes to zero as $n \to \infty $. Hence the method tends to give nearly optimal solutions when the number of cities is extremely large.