Belief propagation for optimal edge cover in the random complete graph
type: Item
instance of: scholarly article
title: Belief propagation for optimal edge cover in the random complete graph
zbMATH Open document ID: 1318.60016
DOI: 10.1214/13-AAP981
author: Mustafa Khandwawala
author: Rajesh Sundaresan
published in: The Annals of Applied Probability
publication date: 2014-11-21T00:00:00Z
full work available at URL: https://arxiv.org/abs/1212.6027
full work available at URL: https://projecteuclid.org/euclid.aoap/1409058036
review text: This article studies the minimum cost edge cover problem on the complete graph, where the edge costs are random independent and identically distributed. The article begins with a review of the literature on the problem, followed by a presentation of the main result which is the limit of the optimal cost as the number of vertices goes to infinity. Moreover, it is established that a belief propagation algorithm, presented in the article, provides an edge cover which is asymptotically optimal as the number of vertices goes to infinity. The authors provide a very large number of useful results via proven theorems. A list of useful references concludes this interesting article.
reviewed by: Efstratios Rappos
Mathematics Subject Classification ID: 60C05
Mathematics Subject Classification ID: 68Q87
Mathematics Subject Classification ID: 82B44
Mathematics Subject Classification ID: 05C80
zbMATH DE Number: 6371854
zbMATH Keywords: belief propagation
zbMATH Keywords: edge cover
zbMATH Keywords: local weak convergence
zbMATH Keywords: objective method
zbMATH Keywords: semantic projection
MaRDI profile type: Publication
arXiv ID: 1212.6027
cites work: Asymptotics in the random assignment problem
cites work: Processes on unimodular random networks
cites work: Q4450065
cites work: The \(\zeta(2)\) limit in the random assignment problem
cites work: A survey of max-type recursive distributional equations
cites work: Endogeny for the logistic recursive distributional equation
cites work: Max-Product for Maximum Weight Matching: Convergence, Correctness, and LP Duality
cites work: On the value of a random minimum spanning tree problem
cites work: Performance of global load balancing by local adjustment
cites work: Edge cover and polymatroid flow problems
cites work: Cross-lingual Annotation Projection for Semantic Roles
cites work: Belief Propagation: An Asymptotically Optimal Algorithm for the Random Assignment Problem
cites work: Combinatorial optimization. Polyhedra and efficiency (3 volumes)
cites work: The mean field traveling salesman and related problems
cites work: Replica symmetry of the minimum matching
description: scientific article