North-Holland Analysis of Christofides ' heuristic: Some paths are more difficult than cycles

For the traveling salesman problem in which the distances atisfy the triangle inequality, Christofides ' heuristic produces a tour whose length is guaranteed to be less than ~ times the optimum tour length. We investigate the performance of appropriate modifications of this heuristic for the problem of finding a shortest Hamiltonian path. There are three variants of this problem, depending on the number of prespecified endpoints: zero, one, or two. It is not hard to see that, for the first two problems, the 5 worst-case performance ratio of a Christofides-like heuristic is still 7-3 For the third case, we show that the ratio is 3 and that this bound is tight. traveling salesman problem; Hamiltonian cycle; Hamiltonian path; approximation algorithm; worst-case analysis. 1