We show that the average optimal cost for the traveling salesman problem in two dimensions, which is the archetypal problem in combinatorial optimization, in the bipartite case, is simply related to the average optimal cost of the assignment problem with the same Euclidean, increasing, convex weights. In this way we extend a result already known in one dimension where exact solutions are available. The recently determined average optimal cost for the assignment when the cost function is the square of the distance between the points provides therefore an exact prediction EN=1πlogN for large number of points 2N. As a by-product of our analysis, also the loop covering problem has the same optimal average cost. We also explain why this result cannot be extended to higher dimensions. We numerically check the exact predictions.

Exact value for the average optimal cost of the bipartite traveling salesman and two-factor problems in two dimensions / R. Capelli, S. Caracciolo, A. DI GIOACCHINO, E.M. Malatesta. - In: PHYSICAL REVIEW. E. - ISSN 2470-0045. - 98:3(2018 Sep 27), pp. 030101.030101-1-030101.030101-5. [10.1103/PhysRevE.98.030101]

Exact value for the average optimal cost of the bipartite traveling salesman and two-factor problems in two dimensions

R. Capelli
Primo
;
S. Caracciolo
Secondo
;
A. DI GIOACCHINO
Penultimo
;
E.M. Malatesta
Ultimo
2018

Abstract

We show that the average optimal cost for the traveling salesman problem in two dimensions, which is the archetypal problem in combinatorial optimization, in the bipartite case, is simply related to the average optimal cost of the assignment problem with the same Euclidean, increasing, convex weights. In this way we extend a result already known in one dimension where exact solutions are available. The recently determined average optimal cost for the assignment when the cost function is the square of the distance between the points provides therefore an exact prediction EN=1πlogN for large number of points 2N. As a by-product of our analysis, also the loop covering problem has the same optimal average cost. We also explain why this result cannot be extended to higher dimensions. We numerically check the exact predictions.
Physics - Disordered Systems and Neural Networks; Physics - Disordered Systems and Neural Networks; Statistical and Nonlinear Physics; Statistics and Probability; Condensed Matter Physics
Settore FIS/02 - Fisica Teorica, Modelli e Metodi Matematici
Human Brain Project Specific Grant Agreement 1 (HBP SGA1)
Human Brain Project Specific Grant Agreement 2 (HBP SGA2)
Article (author)
File in questo prodotto:
File Dimensione Formato  
p174.pdf

accesso aperto

Tipologia: Publisher's version/PDF
Dimensione 564.73 kB
Formato Adobe PDF
564.73 kB Adobe PDF Visualizza/Apri
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: https://hdl.handle.net/2434/596178
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 3
  • ???jsp.display-item.citation.isi??? 4
social impact