Fluctuations in the random-link matching problem

Abstract

Using the replica approach and the cavity method, we study the fluctuations of the optimal cost in the random-link matching problem. By means of replica arguments, we derive the exact expression of its variance. Moreover, we study the large deviation function, deriving its expression in two different ways, namely using both the replica method and the cavity method.

arXiv comment9 pages, 3 figures

References in corpus (14)

• The Bethe lattice spin glass revisited
• Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
• The random K-satisfiability problem: from an analytic solution to an efficient algorithm
• The number of matchings in random graphs
• Topology trivialization and large deviations for the minimum in the simplest random optimization
• Large Deviations in the Free-Energy of Mean-Field Spin-Glasses
• Phase diagram and large deviations in the free-energy of mean-field spin-glasses
• On the finite size corrections to some random matching problems
• Universality and Deviations in Disordered Systems
• The cavity method for large deviations
• Neighborhood preferences in random matching problems
• One-loop diagrams in the Random Euclidean Matching Problem
• Finite-size corrections in the random assignment problem
• The Random Fractional Matching Problem

Cited by in corpus (5)

• Phase transitions in the mini-batch size for sparse and dense two-layer neural networks
• Large deviations of the free energy in the p-spin glass spherical model
• Random-link matching problems on random regular graphs
• Replica-symmetry breaking transitions in the large deviations of the ground-state of a spherical spin-glass
• Large Deviation Properties of Minimum Spanning Trees for Random Graphs