Analysis of Christofides' heuristic: some paths are more difficult than cycles (Q1180833): Difference between revisions

Christofides proposed a heuristic for the travelling salesman problem in which the distances satisfy the triangle inequality that produces a cycle with a length that is less than \(3/2\) times the optimum cycle length. The author deals with the problem of finding a Hamiltonian path of minimum total length with zero, one or two prespecified endpoints and formulates Christofides-like algorithms for each of these three problems. It is easy to see that the heuristic is still a \(3/2\)-approximation algorithm for the problems with zero and one endpoint. For the third case the worst performance ratio is shown to be \(5/3\) and it is shown that this bound is tight.