Sharp bounds for Karp's “patching”-algorithm for the approximate solution of the traveling salesman problem

Abstract

We shall give a complete “worst case” analysis of Karp's algorithm and show that, if symmetry and triangular inequality are valid, the relative error of the length of an optimal tour with respect to the length of the approximate tour found is 2. If we use a modified method of patching of the subtours then this bound can be substantially reduced at the same cost. In the asymmetric case analogous improvements appear.

Keywords:

• Traveling salesman problem
• Karp's algorithm
• analysis of the worst case

AMS 1980 Subject Classifications:

• Primary: 05 C 35
• Secondary: 90 C 08
• Secondary: 90 C 35