We propose a simple yet very predictive form, based on a Poisson's equation, for the functional dependence of the cost from the density of points in the Euclidean bipartite matching problem. This leads, for quadratic costs, to the analytic prediction of the large N limit of the average cost in dimension d=1,2 and of the subleading correction in higher dimension. A nontrivial scaling exponent, γd=d−2d, which differs from the monopartite's one, is found for the subleading correction. We argue that the same scaling holds true for a generic cost exponent in dimension d>2.

Scaling hypothesis for the Euclidean bipartite matching problem / S. Caracciolo, C. Lucibello, G. Parisi, G. Sicuro. - In: PHYSICAL REVIEW E, STATISTICAL, NONLINEAR, AND SOFT MATTER PHYSICS. - ISSN 1539-3755. - 90:1(2014 Jul 21), pp. 012118.1-012118.9.

Scaling hypothesis for the Euclidean bipartite matching problem

S. Caracciolo
Primo
;
2014

Abstract

We propose a simple yet very predictive form, based on a Poisson's equation, for the functional dependence of the cost from the density of points in the Euclidean bipartite matching problem. This leads, for quadratic costs, to the analytic prediction of the large N limit of the average cost in dimension d=1,2 and of the subleading correction in higher dimension. A nontrivial scaling exponent, γd=d−2d, which differs from the monopartite's one, is found for the subleading correction. We argue that the same scaling holds true for a generic cost exponent in dimension d>2.
Settore FIS/02 - Fisica Teorica, Modelli e Metodi Matematici
21-lug-2014
Article (author)
File in questo prodotto:
Non ci sono file associati a questo prodotto.
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/238191
Citazioni
  • ???jsp.display-item.citation.pmc??? 1
  • Scopus 47
  • ???jsp.display-item.citation.isi??? 46
social impact