×

Analysis of Christofides’ heuristic: some paths are more difficult than cycles. (English) Zbl 0748.90071

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.

MSC:

90C35 Programming involving graphs or networks
68W25 Approximation algorithms
90C59 Approximation methods and heuristics in mathematical programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Christofides, N., Worst-case analysis of a new heuristic for the travelling salesman problem, (Report 388, Graduate School of Industrial Administration (1976), Carnegie-Mellon University: Carnegie-Mellon University Pittsburgh, PA) · Zbl 0506.90059
[2] Cornuéjols, G.; Nemhauser, G. L., Tight bounds for Christofides’ traveling salesman heuristic, Math. Programming, 14, 116-121 (1978) · Zbl 0396.90098
[3] Johnson, D. S.; Papadimitriou, C. H., Performance guarantees for heuristics, (Lawler, E. L.; Lenstra, J. K.; Rinnooy Kan, A. H.G.; Shmoys, D. B., The Traveling Salesman Problem: a Guided Tour of Combinatorial Optimization (1985), Wiley: Wiley Chichester), 145-180 · Zbl 0574.90086
[4] Sahni, S.; Gonzalez, T., P-complete approximation problems, J. Assoc. Comput. Mach., 23, 555-565 (1976) · Zbl 0348.90152
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.