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

J.A. Hoogeveen

    Research output: Contribution to journalArticleAcademicpeer-review

    123 Citations (Scopus)
    3 Downloads (Pure)

    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 3/2 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 worst-case performance ratio of a Christofides-like heuristic is still 3/2. For the third case, we show that the ratio is 5/3 and that this bound is tight.
    Original languageEnglish
    Pages (from-to)291-295
    Number of pages5
    JournalOperations Research Letters
    Volume10
    Issue number5
    DOIs
    Publication statusPublished - 1991

    Fingerprint

    Dive into the research topics of 'Analysis of Christofides' heuristic : some paths are more difficult than cycles'. Together they form a unique fingerprint.

    Cite this