Quasiabelian landscapes of the traveling salesman problem are elementary

Publisher:
Elsevier Science Bv
Publication Type:
Journal Article
Citation:
Discrete Optimisation, 2009, 6 (3), pp. 288 - 291
Issue Date:
2009-01
Full metadata record
Files in This Item:
Filename Description Size
Thumbnail2008007810OK.pdf297.57 kB
Adobe PDF
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: