Skip navigation
Skip navigation
A change is coming. Click to see a sneak peek of the new Open Research Repository.

The backbone of the travelling salesperson

Request a Copy

link to publisher version

Kilby, Philip; Slaney, John K; Walsh, Toby

Description

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

dc.contributor.authorKilby, Philip
dc.contributor.authorSlaney, John K
dc.contributor.authorWalsh, Toby
dc.coverage.spatialEdinburgh Scotland
dc.date.accessioned2015-12-10T22:12:27Z
dc.date.created30 July - 5 Augusut 2005
dc.identifier.isbn0938075934
dc.identifier.urihttp://hdl.handle.net/1885/49661
dc.description.abstractWe 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
dc.publisherAAAI Press
dc.relation.ispartofseriesInternational Joint Conference on Artificial Intelligence (IJCAI 2005)
dc.sourceProceedings of the 19th International Joint Conference on Artificial Intelligence (IJCAI 2005)
dc.source.urihttp://ijcai.org/Past%20Proceedings/IJCAI-05/IJCAI-05%20CONTENT.htm
dc.source.urihttp://www.ijcai.org/search.php
dc.subjectKeywords: Approximation methods; Optimal solutions; Optimality; Optimization problems; Performance guarantees; Runtimes; Artificial intelligence; Optimization; Optimal systems
dc.titleThe backbone of the travelling salesperson
dc.typeConference paper
local.description.notesImported from ARIES
local.description.refereedYes
dc.date.issued2005
local.identifier.absfor080199 - Artificial Intelligence and Image Processing not elsewhere classified
local.identifier.ariespublicationMigratedxPub190
local.type.statusPublished Version
local.contributor.affiliationKilby, Philip, College of Engineering and Computer Science, ANU
local.contributor.affiliationSlaney, John K, College of Engineering and Computer Science, ANU
local.contributor.affiliationWalsh, Toby, University of York
local.description.embargo2037-12-31
local.bibliographicCitation.startpage175
local.bibliographicCitation.lastpage180
dc.date.updated2016-02-24T09:48:18Z
local.identifier.scopusID2-s2.0-84880712829
CollectionsANU Research Publications

Download

File Description SizeFormat Image
01_Kilby_The_backbone_of_the_travelling_2005.pdf1.03 MBAdobe PDF    Request a copy
02_Kilby_The_backbone_of_the_travelling_2005.pdf238.8 kBAdobe PDF    Request a copy
03_Kilby_The_backbone_of_the_travelling_2005.pdf1.4 MBAdobe PDF    Request a copy
Show simple item record


Items in Open Research are protected by copyright, with all rights reserved, unless otherwise indicated.

Updated:  17 November 2022/ Responsible Officer:  University Librarian/ Page Contact:  Library Systems & Web Coordinator