Quasiabelian landscapes of the traveling salesman problem are elementary

Solomon, AI; Colletti, B

Quasiabelian landscapes of the traveling salesman problem are elementary

Solomon, AI Colletti, B

Permalink

Publisher:: Elsevier Science Bv
Publication Type:: Journal Article
Citation:: Discrete Optimisation, 2009, 6 (3), pp. 288 - 291
Issue Date:: 2009-01

Closed Access

	Filename	Description	Size
	2008007810OK.pdf		297.57 kB	Adobe PDF	View/Open

Copyright Clearance Process

Recently Added
In Progress
Closed Access

This item is closed access and not available.

Full metadata record

Field	Value	Language
dc.contributor.author	Solomon, AI	en_US
dc.contributor.author	Colletti, B	en_US
dc.date.issued	2009-01	en_US
dc.identifier.citation	Discrete Optimisation, 2009, 6 (3), pp. 288 - 291	en_US
dc.identifier.issn	1572-5286	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.	en_US
dc.publisher	Elsevier Science Bv	en_US
dc.relation.ispartof	Discrete Optimisation	en_US
dc.relation.isbasedon	10.1016/j.disopt.2009.02.001	en_US
dc.subject.classification	Operations Research	en_US
dc.title	Quasiabelian landscapes of the traveling salesman problem are elementary	en_US
dc.type	Journal Article
utslib.citation.volume	3	en_US
utslib.citation.volume	6	en_US
utslib.location.activity	ISI:000267412700005	en_US
utslib.for	0101 Pure Mathematics	en_US
utslib.for	0102 Applied Mathematics	en_US
utslib.for	0103 Numerical and Computational Mathematics	en_US
dc.location.activity	ISI:000267412700005	en_US
pubs.embargo.period	Not known	en_US
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 Electrical and Data Engineering
utslib.copyright.status	closed_access
pubs.consider-herdc	true	en_US
pubs.issue	3	en_US
pubs.volume	6	en_US

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.

Please use this identifier to cite or link to this item:

http://hdl.handle.net/10453/8783