The traveling salesman problem: The spectral radius and the length of an optimal tour


Dragoš Cvetković, Zorica Dražić, Vera Kovačević-Vujčić, Mirjana Čangalović




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.