The planted matching problem: phase transitions and exact results
DOI10.1214/20-AAP1660zbMath1485.90115arXiv1912.08880OpenAlexW2996682353MaRDI QIDQ2075325
Jiaming Xu, Mehrdad Moharrami, Moore, Cristopher
Publication date: 14 February 2022
Published in: The Annals of Applied Probability (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1912.08880
combinatorial optimizationphase transitionsrandom graphslocal weak convergencemessage-passing algorithmsplanted problems
Bayesian inference (62F15) Random graphs (graph-theoretic aspects) (05C80) Combinatorial optimization (90C27) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Phase transitions (general) in equilibrium statistical mechanics (82B26) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Belief propagation for optimal edge cover in the random complete graph
- The mean field traveling salesman and related problems
- Near-minimal spanning trees: A scaling exponent in probability models
- An easy proof of the \(\zeta (2)\) limit in the random assignment problem
- Asymptotics in the random assignment problem
- Certain expected values in the random assignment problem
- A proof of Parisi's conjecture on the random assignment problem
- Linear phase transition in random linear constraint satisfaction problems
- Concentration of measure and isoperimetric inequalities in product spaces
- Sudden emergence of a giant \(k\)-core in a random graph
- Processes on unimodular random networks
- The ?(2) limit in the random assignment problem
- On the Expected Value of a Random Assignment Problem
- Belief Propagation: An Asymptotically Optimal Algorithm for the Random Assignment Problem
- Maximum weight independent sets and matchings in sparse random graphs. Exact results using the local weak convergence method
- Invariant probability measures and dynamics of exponential linear type maps
- Dynamic Programming Optimization over Random Data: The Scaling Exponent for Near-Optimal Solutions
- On Approximation Methods for the Assignment Problem
- Community Detection and Stochastic Block Models
- A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem
- A proof of a conjecture of Buck, Chan, and Robbins on the expected value of the minimum assignment
- Real Analysis and Probability
- The Computer Science and Physics of Community Detection: Landscapes, Phase Transitions, and Hardness
- A Lower Bound on the Expected Cost of an Optimal Assignment
- Scaling and universality in continuous length combinatorial optimization
- Proofs of the Parisi and Coppersmith‐Sorkin random assignment conjectures
- A Note on the Theory of Moment Generating Functions
This page was built for publication: The planted matching problem: phase transitions and exact results
