Quasiabelian landscapes of the traveling salesman problem are elementary

DSpace/Manakin Repository

Search OPUS


Advanced Search

Browse

My Account

Show simple item record

dc.contributor.author Solomon, AI
dc.contributor.author Colletti, B
dc.date.accessioned 2010-05-28T09:45:26Z
dc.date.issued 2009-01
dc.identifier.citation Discrete Optimisation, 2009, 6 (3), pp. 288 - 291
dc.identifier.issn 1572-5286
dc.identifier.other C1 en_US
dc.identifier.uri http://hdl.handle.net/10453/8783
dc.description.abstract Regarding a permutation as a (multi-traveler) tour of the traveling salesman problem, we show that-regardless of the distance matrix-the landscape based on a quasiabelian Cayley graph belongs to the class of elementary landscapes, where the cost vector is an eigenvector of the Cayley Laplacian, and where local minima are below average. The quasiabelian case has the additional property that, because the cost vector is an eigenvector of the Cayley Laplacian, the landscape can be reduced into independent components under a Fourier transformation. We indicate the way this may result in parallel (and therefore computationally distributed) traversal of the landscape.
dc.publisher Elsevier Science Bv
dc.relation.isbasedon 10.1016/j.disopt.2009.02.001
dc.subject Traveling salesman problem, TSP, Permutation, Group representation, Landscape, Elementary, Eigenvector, Eigenvalue, Quasiabelian, Operations Research
dc.subject Traveling salesman problem; TSP; Permutation; Group representation; Landscape; Elementary; Eigenvector; Eigenvalue; Quasiabelian; Operations Research
dc.title Quasiabelian landscapes of the traveling salesman problem are elementary
dc.type Journal Article
dc.parent Discrete Optimisation
dc.journal.volume 3
dc.journal.volume 6
dc.journal.number 3 en_US
dc.publocation Amsterdam, The Netherlands en_US
dc.identifier.startpage 288 en_US
dc.identifier.endpage 291 en_US
dc.cauo.name FEIT.School of Systems, Management and Leadership en_US
dc.conference Verified OK en_US
dc.for 0101 Pure Mathematics
dc.personcode 010771 en_US
dc.personcode 0000052834 en_US
dc.percentage 100 en_US
dc.classification.name Pure Mathematics en_US
dc.classification.type FOR-08 en_US
dc.edition en_US
dc.custom en_US
dc.date.activity en_US
dc.location.activity ISI:000267412700005 en_US
dc.location.activity ISI:000267412700005
dc.description.keywords Traveling salesman problem; TSP; Permutation; Group representation; Landscape; Elementary; Eigenvector; Eigenvalue; Quasiabelian en_US
dc.description.keywords Traveling salesman problem
dc.description.keywords TSP
dc.description.keywords Permutation
dc.description.keywords Group representation
dc.description.keywords Landscape
dc.description.keywords Elementary
dc.description.keywords Eigenvector
dc.description.keywords Eigenvalue
dc.description.keywords Quasiabelian
dc.staffid en_US
pubs.embargo.period Not known
pubs.organisational-group /University of Technology Sydney
pubs.organisational-group /University of Technology Sydney/Faculty of Engineering and Information Technology
pubs.organisational-group /University of Technology Sydney/Faculty of Engineering and Information Technology/School of Computing and Communications


Files in this item

This item appears in the following Collection(s)

Show simple item record