Belief propagation for optimal edge cover in the random complete graph

DOI10.1214/13-AAP981zbMath1318.60016arXiv1212.6027MaRDI QIDQ473162

Rajesh Sundaresan, Mustafa Khandwawala

Publication date: 21 November 2014

Published in: The Annals of Applied Probability (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1212.6027

zbMATH Keywords

edge coverlocal weak convergenceobjective methodbelief propagationsemantic projection

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05) Disordered systems (random Ising models, random Schrödinger operators, etc.) in equilibrium statistical mechanics (82B44) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items (3)

Central limit theorems for combinatorial optimization problems on sparse Erdős-Rényi graphs ⋮ The planted matching problem: phase transitions and exact results ⋮ The densest subgraph problem in sparse random graphs

Cites Work

• Unnamed Item
• Replica symmetry of the minimum matching
• Endogeny for the logistic recursive distributional equation
• A survey of max-type recursive distributional equations
• The mean field traveling salesman and related problems
• Edge cover and polymatroid flow problems
• On the value of a random minimum spanning tree problem
• Asymptotics in the random assignment problem
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Processes on unimodular random networks
• The ?(2) limit in the random assignment problem
• Belief Propagation: An Asymptotically Optimal Algorithm for the Random Assignment Problem
• Performance of global load balancing by local adjustment
• Max-Product for Maximum Weight Matching: Convergence, Correctness, and LP Duality
• Cross-lingual Annotation Projection for Semantic Roles

This page was built for publication: Belief propagation for optimal edge cover in the random complete graph