The backbone of the travelling salesperson
Date
Authors
Kilby, Philip
Slaney, John K
Walsh, Toby
Journal Title
Journal ISSN
Volume Title
Publisher
AAAI Press
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. Nevert
Description
Citation
Collections
Source
Proceedings of the 19th International Joint Conference on Artificial Intelligence (IJCAI 2005)
Type
Book Title
Entity type
Access Statement
License Rights
DOI
Restricted until
2037-12-31