  We apply the objective method of Aldous to the problem of finding the
minimum-cost edge cover of the complete graph with random independent and
identically distributed edge costs. The limit, as the number of vertices goes
to infinity, of the expected minimum cost for this problem is known via a
combinatorial approach of Hessler and W\"{a}stlund. We provide a proof of this
result using the machinery of the objective method and local weak convergence,
which was used to prove the $\zeta(2)$ limit of the random assignment problem.
A proof via the objective method is useful because it provides us with more
information on the nature of the edge's incident on a typical root in the
minimum-cost edge cover. We further show that a belief propagation algorithm
converges asymptotically to the optimal solution. This can be applied in a
computational linguistics problem of semantic projection. The belief
propagation algorithm yields a near optimal solution with lesser complexity
than the known best algorithms designed for optimality in worst-case settings.
