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

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

0.00 Avg rating0 Votes
Article ID: iaor1992265
Country: Netherlands
Volume: 10
Issue: 5
Start Page Number: 291
End Page Number: 295
Publication Date: Jul 1991
Journal: Operations Research Letters
Authors:
Abstract:

For the traveling salesman problem in which the distances satisfy the triangle inequality, Christofides' heuristic produces a tour whose length is guaranteed to be less than equ1times the optimum tour length. The paper investigates 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 worst-case performance ratio of a Christofides-like heuristic is still equ2. For the third case, the paper shows that the ratio is equ3and that this bound is tight.

Reviews

Required fields are marked *. Your email address will not be published.