Central limit theorems for combinatorial optimization problems on sparse Erdős-Rényi graphs

DOI10.1214/20-AAP1630zbMath1482.60034arXiv1905.08366OpenAlexW3199910074WikidataQ113752026 ScholiaQ113752026MaRDI QIDQ2240864

Sky Cao

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

zbMATH Keywords

combinatorial optimizationStein's methodcentral limit theoremreplica symmetrymaximum weight matchingErdős-Rényi graphendogenyminimum matchinggeneralized perturbative approachlong-range independenceoptimal edge cover

Mathematics Subject Classification ID

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