UNIVERSAL FLUCTUATIONS OF QUASI-OPTIMAL PATHS OF THE TRAVELING SALESMAN PROBLEM

We study the statistical properties of the quasi-optimal solutions to the travelling salesman problem with city positions randomly distribut ed on a square. To each near-optimal solution we associate points on a circle with the same order and distances. We then analyse the fluctua tions of the positions, applying statistical measures developed previo usly to investigate the behaviour of eigenvalues of (unitary) random m atrices. We establish that, in the limit of a large number of cities, these measures display a universal behaviour, intermediate between tha t of a sequence of uncorrelated random points and a sequence of eigenv alues of unitary symmetric random matrices.