We consider the random Euclidean assignment problem on the line between two sets of N random points, independently generated with the same probability density function ϱ. The cost of the matching is supposed to be dependent on a power p> 1 of the Euclidean distance of the matched pairs. We discuss an integral expression for the average optimal cost for N≫ 1 that generalizes a previous result obtained for p= 2. We also study the possible divergence of the given expression due to the vanishing of the probability density function. The provided regularization recipe allows us to recover the proper scaling law for the cost in the divergent cases, and possibly some of the involved coefficients. The possibility that the support of ϱ is a disconnected interval is also analysed. We exemplify the proposed procedure and we compare our predictions with the results of numerical simulations.

Anomalous Scaling of the Optimal Cost in the One-Dimensional Random Assignment Problem / S. Caracciolo, M. D’Achille, G. Sicuro. - In: JOURNAL OF STATISTICAL PHYSICS. - ISSN 0022-4715. - 174:4(2019 Feb), pp. 846-864.

Anomalous Scaling of the Optimal Cost in the One-Dimensional Random Assignment Problem

Caracciolo, Sergio;
2019-02

Abstract

We consider the random Euclidean assignment problem on the line between two sets of N random points, independently generated with the same probability density function ϱ. The cost of the matching is supposed to be dependent on a power p> 1 of the Euclidean distance of the matched pairs. We discuss an integral expression for the average optimal cost for N≫ 1 that generalizes a previous result obtained for p= 2. We also study the possible divergence of the given expression due to the vanishing of the probability density function. The provided regularization recipe allows us to recover the proper scaling law for the cost in the divergent cases, and possibly some of the involved coefficients. The possibility that the support of ϱ is a disconnected interval is also analysed. We exemplify the proposed procedure and we compare our predictions with the results of numerical simulations.
Physics - Disordered Systems and Neural Networks; Physics - Disordered Systems and Neural Networks; Mathematical Physics; Mathematics - Mathematical Physics; Statistical and Nonlinear Physics; Mathematical Physics
Settore FIS/02 - Fisica Teorica, Modelli e Metodi Matematici
Article (author)
File in questo prodotto:
File Dimensione Formato  
Corrections1d.pdf

embargo fino al 28/05/2020

Tipologia: Post-print, accepted manuscript ecc. (versione accettata dall'editore)
Dimensione 856.52 kB
Formato Adobe PDF
856.52 kB Adobe PDF Visualizza/Apri
Caracciolo2019_Article_AnomalousScalingOfTheOptimalCo.pdf

non disponibili

Tipologia: Publisher's version/PDF
Dimensione 1.67 MB
Formato Adobe PDF
1.67 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/634436
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 5
  • ???jsp.display-item.citation.isi??? 4
social impact