The backbone of the travelling salesperson

Philip Kilby, John Slaney, Toby Walsh

    Research output: Contribution to journalConference articlepeer-review

    38 Citations (Scopus)

    Abstract

    We study the backbone of the travelling salesperson optimization problem. We prove that it is intractable to approximate the backbone with any performance guarantee, assuming that P≠NP and there is a limit on the number of edges falsely returned. Nevertheless, in practice, it appears that much of the backbone is present in close to optimal solutions. We can therefore often find much of the backbone using approximation methods based on good heuristics. We demonstrate that such backbone information can be used to guide the search for an optimal solution. However, the variance in runtimes when using a backbone guided heuristic is large. This suggests that we may need to combine such heuristics with randomization and restarts. In addition, though backbone guided heuristics are useful for finding optimal solutions, they are less help in proving optimality.

    Original languageEnglish
    Pages (from-to)175-180
    Number of pages6
    JournalIJCAI International Joint Conference on Artificial Intelligence
    Publication statusPublished - 2005
    Event19th International Joint Conference on Artificial Intelligence, IJCAI 2005 - Edinburgh, United Kingdom
    Duration: 30 Jul 20055 Aug 2005

    Fingerprint

    Dive into the research topics of 'The backbone of the travelling salesperson'. Together they form a unique fingerprint.

    Cite this