The traveling salesman problem: The spectral radius and the length of an optimal tour
Апстракт
We consider the symmetric traveling salesman problem (TSP) with instances represented by complete graphs with distances between cities as edge weights. Computational experiments with randomly generated instances on 50 and 100 vertices with the
uniform distribution of integer edge weights in interval [1, 100] show that there exists a correlation between the sequences of the spectral radii of the distance matrices and the lengths
of optimal tours obtained by the well known TSP solver Concorde. In this paper we give a
partial theoretical explanation of this correlation.
Кључне речи:
Traveling salesman problem / Spectra of graphs / Spectral radius / Concorde TSP solverИзвор:
Bulletin T.CLI de l’Académie serbe des sciences et des arts, 2018, 17-26Издавач:
- Beograd : Académie Serbe des sciences et des arts
Финансирање / пројекти:
- Математички Модели и Методе Оптимизације Великих Система (RS-MESTD-Basic Research (BR or ON)-174010)
- Теорија графова и математичко програмирање са применама у хемији и рачунарству (RS-MESTD-Basic Research (BR or ON)-174033)
- Serbian Academy of Sciences and Arts, Project F-159
Напомена:
- Bulletin de l'Académie serbe des sciences. Classe des sciences mathématiques et naturelles. Sciences mathématiques. . - 43 , 151 (2018)
TY - CONF AU - Cvetković, Dragoš AU - Dražić, Zorica AU - Kovačević-Vujčić, Vera AU - Čangalović, Mirjana PY - 2018 UR - https://dais.sanu.ac.rs/123456789/9081 AB - We consider the symmetric traveling salesman problem (TSP) with instances represented by complete graphs with distances between cities as edge weights. Computational experiments with randomly generated instances on 50 and 100 vertices with the uniform distribution of integer edge weights in interval [1, 100] show that there exists a correlation between the sequences of the spectral radii of the distance matrices and the lengths of optimal tours obtained by the well known TSP solver Concorde. In this paper we give a partial theoretical explanation of this correlation. PB - Beograd : Académie Serbe des sciences et des arts C3 - Bulletin T.CLI de l’Académie serbe des sciences et des arts T1 - The traveling salesman problem: The spectral radius and the length of an optimal tour SP - 17 EP - 26 UR - https://hdl.handle.net/21.15107/rcub_dais_9081 ER -
@conference{ author = "Cvetković, Dragoš and Dražić, Zorica and Kovačević-Vujčić, Vera and Čangalović, Mirjana", year = "2018", abstract = "We consider the symmetric traveling salesman problem (TSP) with instances represented by complete graphs with distances between cities as edge weights. Computational experiments with randomly generated instances on 50 and 100 vertices with the uniform distribution of integer edge weights in interval [1, 100] show that there exists a correlation between the sequences of the spectral radii of the distance matrices and the lengths of optimal tours obtained by the well known TSP solver Concorde. In this paper we give a partial theoretical explanation of this correlation.", publisher = "Beograd : Académie Serbe des sciences et des arts", journal = "Bulletin T.CLI de l’Académie serbe des sciences et des arts", title = "The traveling salesman problem: The spectral radius and the length of an optimal tour", pages = "17-26", url = "https://hdl.handle.net/21.15107/rcub_dais_9081" }
Cvetković, D., Dražić, Z., Kovačević-Vujčić, V.,& Čangalović, M.. (2018). The traveling salesman problem: The spectral radius and the length of an optimal tour. in Bulletin T.CLI de l’Académie serbe des sciences et des arts Beograd : Académie Serbe des sciences et des arts., 17-26. https://hdl.handle.net/21.15107/rcub_dais_9081
Cvetković D, Dražić Z, Kovačević-Vujčić V, Čangalović M. The traveling salesman problem: The spectral radius and the length of an optimal tour. in Bulletin T.CLI de l’Académie serbe des sciences et des arts. 2018;:17-26. https://hdl.handle.net/21.15107/rcub_dais_9081 .
Cvetković, Dragoš, Dražić, Zorica, Kovačević-Vujčić, Vera, Čangalović, Mirjana, "The traveling salesman problem: The spectral radius and the length of an optimal tour" in Bulletin T.CLI de l’Académie serbe des sciences et des arts (2018):17-26, https://hdl.handle.net/21.15107/rcub_dais_9081 .