Belief propagation for optimal edge cover in the random complete graph (Q473162)

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.