Belief propagation for optimal edge cover in the random complete graph (Q473162): Difference between revisions

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.