2016/09/30 by Carlo Lucibello, Giorgio Parisi, Gabriele Sicuro · 1 citation
Computer Science · Mathematics · Physics and Astronomy · #Combinatorics #Complexity and Algorithms in Graphs #Computer science #Euclidean distance #Euclidean distance matrix #Euclidean geometry #Euclidean space #Geometry #Loop (graph theory) #Markov Chains and Monte Carlo Methods #Matching (statistics) #Mathematical optimization #Mathematics #Optimization and Search Problems #Replica #Set (abstract data type) #Space (punctuation) #Statistics #cond-mat.dis-nn #cs.DM
paper · pdf · doi:10.1103/physreve.95.012302
published as Phys. Rev. E 95, 012302 (2017) · 17 pages, 7 figures
arxiv created 2016/10/01 · openalex publication_date 2017/01/03 · arxiv updated 2017/01/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
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.