One-loop diagrams in the Random Euclidean Matching Problem

Abstract

The matching problem is a notorious combinatorial optimization problem that has attracted for many years the attention of the statistical physics community. Here we analyze the Euclidean version of the problem, i.e. the optimal matching problem between points randomly distributed on a $d$-dimensional Euclidean space, where the cost to minimize depends on the points' pairwise distances. Using Mayer's cluster expansion we write a formal expression for the replicated action that is suitable for a saddle point computation. We give the diagrammatic rules for each term of the expansion, and we analyze in detail the one-loop diagrams. A characteristic feature of the theory, when diagrams are perturbatively computed around the mean field part of the action, is the vanishing of the mass at zero momentum. In the non-Euclidean case of uncorrelated costs instead, we predict and numerically verify an anomalous scaling for the sub-sub-leading correction to the asymptotic average cost.

17 pages, 7 figures

References in corpus (19)

• Maximum Weight Matching via Max-Product Belief Propagation
• Network Controllability Is Determined by the Density of Low In-Degree and Out-Degree Nodes
• The number of matchings in random graphs
• The Quantum Adiabatic Algorithm applied to random optimization problems: the quantum spin glass perspective
• Scaling hypothesis for the Euclidean bipartite matching problem
• Random multi-index matching problems
• Cluster expansion in the canonical ensemble
• Scaling hypothesis for the Euclidean bipartite matching problem II. Correlation functions
• Comparing Mean Field and Euclidean Matching Problems
• The stochastic matching problem
• Finite size corrections to disordered systems on Erdös-Rényi random graphs
• On the one dimensional Euclidean matching problem: exact solutions, correlation functions and universality
• On the finite size corrections to some random matching problems
• Quadratic stochastic Euclidean bipartite matching problem
• Correlation function for the Grid-Poisson Euclidean matching on a line and on a circle
• Replica structure of one--dimensional Ising models
• Neighborhood preferences in random matching problems
• One-dimensional disordered Ising models by replica and cavity methods
• Finite Size Corrections to Disordered Systems : mean field results and applications to finite dimensional models

Cited by in corpus (8)

• Random Euclidean matching problems in one dimension
• Solution for a bipartite Euclidean traveling-salesman problem in one dimension
• Finite-size corrections in the random assignment problem
• Fluctuations in the random-link matching problem
• Anomalous scaling of the optimal cost in the one-dimensional random assignment problem
• Random assignment problems on $2d$ manifolds
• Criticality and conformality in the random dimer model
• Random-link matching problems on random regular graphs