Skip to main navigation Skip to search Skip to main content

Scaling hypothesis for the Euclidean bipartite matching problem

  • S. Caracciolo
  • , C. Lucibello
  • , G. Parisi
  • , G. Sicuro
  • University of Milan
  • University of Rome La Sapienza
  • University of Pisa

Research output: Contribution to journalArticlepeer-review

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-2/d, 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.

Original languageEnglish
Article number012118
JournalPhysical Review E - Statistical, Nonlinear, and Soft Matter Physics
Volume90
Issue number1
DOIs
StatePublished - 21 Jul 2014
Externally publishedYes

Fingerprint

Dive into the research topics of 'Scaling hypothesis for the Euclidean bipartite matching problem'. Together they form a unique fingerprint.

Cite this