Belief Propagation: An Asymptotically Optimal Algorithm for the Random Assignment Problem

References

• Aldous D. Asymptotics in the random assignment problem. Probab. Theory Related Fields (1992) 93:507–534Crossref, Google Scholar
• Aldous D. The ζ(2) limit in the random assignment problem. Random Structures Algorithms (2001) 18:381–418Crossref, Google Scholar
• Aldous D., Bandyopadhyay A. A survey of max-type recursive distributional equations. Ann. Appl. Probab. (2005) 15(2):1047–1110Crossref, Google Scholar
• Aldous D., Steele J. M., Kesten H. The objective method: Probabilistic combinatorial optimization and local weak convergence. Probability and Discrete Structures, Vol. 110, Encyclopedia of Mathematical Sciences (2003) (Springer)1–72Google Scholar
• Bandyopadhyay A. Bivariate uniqueness in the logistic recursive distributional equation. (2002) . Technical Report 629, Department of Statistics, University of California, BerkeleyGoogle Scholar
• Bayati M., Shah D., Sharma M. Max-product for maximum weight matching: Convergence, correctness, and LP duality. IEEE Trans. Inform. Theory (2008) 54(3):1241–1251Crossref, Google Scholar
• Billingsley P.Convergence of Probability Measures (1999) (John Wiley & Sons, New York) Wiley Series in Probability and StatisticsCrossref, Google Scholar
• Coppersmith D., Sorkin G. Constructive bounds and exact expectations for the random assignment problem. Random Structures Algorithms (1999) 15:113–144Crossref, Google Scholar
• Dyer M. E., Frieze A. M., McDiarmid C. J. H. On linear programs with random costs. Math. Programming (1986) 35:3–16Crossref, Google Scholar
• Edmonds J., Karp R. Theoretical improvements in algorithmic efficiency for network flow problems. J. ACM (1972) 19:248–264Crossref, Google Scholar
• Goemans M. X., Kodialam M. S. A lower bound on the expected cost of an optimal assignment. Math. Oper. Res. (1993) 18:267–274Link, Google Scholar
• Karp R. M. An algorithm to solve the m × n assignment problem in expected time O(mn log n). Networks (1980) 10:143–152Crossref, Google Scholar
• Karp R. M., Johnson D. An upper bound on the expected cost of an optimal assignment. Discrete Algorithms and Complexity: Proc. Japan-U.S. Joint Seminar (1987) (Academic Press, New York) 1–4Google Scholar
• Lazarus A. Certain expected values in the random assignment problem. Oper. Res. Lett. (1993) 14:207–214Crossref, Google Scholar
• Linusson S., Wästlund J. A proof of Parisi's conjecture on the random assignment problem. Probab. Theory Related Fields (2004) 128:419–440Crossref, Google Scholar
• Mézard M., Parisi G. On the solution of the random link matching problem. J. Phys. (1987) 48:1451–1459Crossref, Google Scholar
• Nair C., Prabhakar B., Sharma M. Proofs of the Parisi and Coppersmith-Sorkin random assignment conjectures. Random Structures Algorithms (2005) 27(4):413–444Crossref, Google Scholar
• Olin B. Asymptotic properties of random assignment problems. (1992) . Ph.D. thesis, Kungl. Tekniska Högskolan, StockholmGoogle Scholar
• Pearl J.Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference (1988) (Morgan Kaufmann, San Francisco) Google Scholar
• Walkup D. W. On the expected value of a random assignment problem. SIAM J. Comput. (1979) 8:440–442Crossref, Google Scholar
• Yedidia J., Freeman W., Weiss Y. Generalized belief propagation. (2000) . Technical Report TR-2000-26, Mitsubishi Electric Research Laboratories, Cambridge, MAGoogle Scholar