## Analysis of a near-metric TSP approximation algorithm^{∗}

Department of Computer Science, ETH Zurich, Switzerland.

sacha.krug@inf.ethz.ch

Received:
18
December
2012

Accepted:
11
July
2013

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 prespecified endpoints, we cannot reuse the example, but
we construct another worst-case example to show the optimality of the analysis also in
this case.

Mathematics Subject Classification: 90C27 / 68W25

Key words: traveling salesman problem / combinatorial optimization / approximation algorithms / graph theory

*© EDP Sciences 2013*