The traveling salesman problem is one of the most studied combinatorial optimization problems, because of the simplicity of its statement and the difficulty in its solution. We study the traveling salesman problem when the positions of the cities are chosen at random in the unit interval and the cost associated with the travel between two cities is their distance elevated to an arbitrary power p is an element of R. We characterize the optimal cycle and compute the average optimal cost for every number of cities when the measure used to choose the position of the cities is flat and asymptotically for large number of cities in the other cases. We also show that the optimal cost is a self-averaging quantity, and we test our analytical results with extensive simulations.

Average optimal cost for the Euclidean TSP in one dimension / S. Caracciolo, A. Di Gioacchino, E.M. Malatesta, C. Vanoni. - In: JOURNAL OF PHYSICS. A, MATHEMATICAL AND THEORETICAL. - ISSN 1751-8113. - 52:26(2019 Jun 28).

Average optimal cost for the Euclidean TSP in one dimension

Caracciolo, Sergio;Di Gioacchino, Andrea;Malatesta, Enrico M;
2019-06-28

Abstract

The traveling salesman problem is one of the most studied combinatorial optimization problems, because of the simplicity of its statement and the difficulty in its solution. We study the traveling salesman problem when the positions of the cities are chosen at random in the unit interval and the cost associated with the travel between two cities is their distance elevated to an arbitrary power p is an element of R. We characterize the optimal cycle and compute the average optimal cost for every number of cities when the measure used to choose the position of the cities is flat and asymptotically for large number of cities in the other cases. We also show that the optimal cost is a self-averaging quantity, and we test our analytical results with extensive simulations.
disordered systems; traveling salesman problem; optimization problems
Settore FIS/02 - Fisica Teorica, Modelli e Metodi Matematici
Article (author)
File in questo prodotto:
File Dimensione Formato  
ETSP-Monopartito-1dv7.pdf

embargo fino al 28/06/2020

Tipologia: Post-print, accepted manuscript ecc. (versione accettata dall'editore)
Dimensione 647.32 kB
Formato Adobe PDF
647.32 kB Adobe PDF Visualizza/Apri
Caracciolo_2019_J._Phys._A__Math._Theor._52_264003.pdf

non disponibili

Tipologia: Publisher's version/PDF
Dimensione 1.72 MB
Formato Adobe PDF
1.72 MB Adobe PDF   Visualizza/Apri   Richiedi una copia
Pubblicazioni consigliate

Caricamento pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/2434/652032
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? 1
social impact