Central limit theorems for combinatorial optimization problems on sparse Erdős-Rényi graphs
DOI10.1214/20-AAP1630zbMath1482.60034arXiv1905.08366OpenAlexW3199910074WikidataQ113752026 ScholiaQ113752026MaRDI QIDQ2240864
Publication date: 4 November 2021
Published in: The Annals of Applied Probability (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1905.08366
combinatorial optimizationStein's methodcentral limit theoremreplica symmetrymaximum weight matchingErdős-Rényi graphendogenyminimum matchinggeneralized perturbative approachlong-range independenceoptimal edge cover
Central limit and other weak theorems (60F05) Random graphs (graph-theoretic aspects) (05C80) Combinatorial optimization (90C27)
Cites Work
- Unnamed Item
- Unnamed Item
- Replica symmetry of the minimum matching
- Belief propagation for optimal edge cover in the random complete graph
- A survey of max-type recursive distributional equations
- The mean field traveling salesman and related problems
- Edge cover and polymatroid flow problems
- A new method of normal approximation
- Ising models on locally tree-like graphs
- Random matching problems on the complete graph
- An easy proof of the \(\zeta (2)\) limit in the random assignment problem
- On the value of a random minimum spanning tree problem
- Probability theory of classical Euclidean optimization problems
- A proof of Parisi's conjecture on the random assignment problem
- A PDE approach to a 2-dimensional matching problem
- Normal approximation for stabilizing functionals
- Central limit theorems in the configuration model
- The RSW theorem for continuum percolation and the CLT for Euclidean minimal spanning trees
- The central limit theorem for weighted minimal spanning trees on random points
- A general method for lower bounds on fluctuations of random variables
- Minimal spanning trees and Stein's method
- Central limit theorems for empirical transportation cost in general dimension
- Belief propagation for minimum weight many-to-one matchings in the random complete graph
- The ?(2) limit in the random assignment problem
- Weighted enumeration of spanning subgraphs in locally tree-like graphs
- Maximum Weight Partial Colorings on Sparse Random Graphs
- Maximum weight independent sets and matchings in sparse random graphs. Exact results using the local weak convergence method
- A short survey of Stein's method
- A proof of a conjecture of Buck, Chan, and Robbins on the expected value of the minimum assignment
- The minimal spanning tree in a complete graph and a functional limit theorem for trees in a random graph
- The random fractional matching problem
- Central limit theorem for statistics of subcritical configuration models
- Limit Theorems in Discrete Stochastic Geometry
- Proofs of the Parisi and Coppersmith‐Sorkin random assignment conjectures
This page was built for publication: Central limit theorems for combinatorial optimization problems on sparse Erdős-Rényi graphs
