ANALYSIS OF A NEAR-METRIC TSP APPROXIMATION ALGORITHM

摘要

The traveling salesman problem (TSP) is one of the most fundamental optimization problems. We consider the β-metric traveling salesman problem (△_β-TSP), i.e., the TSP restricted to graphs satisfying the β-triangle inequality c({v,w}) ≤ β(c({v, u}) + c({u, w})), for some cost function c and any three vertices u, v, w. The well-known path matching Christofides algorithm (PMCA) guarantees an approximation ratio of 3β~2/2 and is the best known algorithm for the △_β-TSP, for 1 ≤ β ≤ 2. We provide a complete analysis of the algorithm. First, we correct an error in the original implementation that may produce an invalid solution. Using a worst-case example, we then show that the algorithm cannot guarantee a better approximation ratio. The example can also be used for the PMCA variants for the Hamiltonian path problem with zero and one prespecified endpoints. For two prespeci-fied endpoints, we cannot reuse the example, but we construct another worst-case example to show the optimality of the analysis also in this case.