Resource Allocation via Message Passing

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 Struct. Algorithms (2001) 18(4):381–418Crossref, Google Scholar
• Aldous D., Steele J. M., Kesten H. The objective method: Probabilistic combinatorial optimization and local weak convergence. Probability on Discrete Structures (2003) (Springer, Berlin) 1–72Google Scholar
• Aliprantis C. D., Tourky R., Yannelis N. C. A theory of value with non-linear prices: Equilibrium analysis beyond vector lattices. J. Econom. Theory (2001) 100(1):22–72Crossref, Google Scholar
• Arrow K. J., Hurwicz L.Studies in Resource Allocation (1977) (Cambridge University Press, Cambridge, UK) Crossref, Google Scholar
• Aurell E., Gordon U., Kirkpatrick S., Saul L. K., Weiss Y., Bottou L. Comparing beliefs, surveys, and random walks. Advances in Neural Information Processing Systems (2005) 17(MIT Press, Cambridge, MA) 49–56Google Scholar
• Bayati M., Shah D., Sharma M. Maximum weight matching via max-product belief propagation. Proc. IEEE Internat. Sympos. Inform. Theory, Adelaide, Australia (2005) (IEEE, New York) 1763–1767Crossref, Google Scholar
• Benedetto S., Divsalar D., Montorsi G., Pollara F. Soft-output decoding algorithms in iterative decoding of turbo codes. (1996) . Telecommunications and Data Acquisition Progress Report 42–142, NASA Jet Propulsion Laboratory, Pasadena, CA, 63–87Google Scholar
• Berliant M., Dunz K. Nonlinear supporting prices: The superadditive case. J. Math. Econom. (1990) 19(4):357–367Crossref, Google Scholar
• Berrou C., Glavieux A., Thitimajshima P. Near Shannon limit error-correcting coding and decoding: Turbo-codes. Proc. IEEE Internat. Comm. Conf., Geneva (1993) 2(IEEE, New York) 1064–1070Crossref, Google Scholar
• Bertsekas D. P.Constrained Optimization and Lagrange Multiplier Methods (1982) (Academic Press, New York) Google Scholar
• Braunstein A., Zecchina R. Survey propagation as local equilibrium equations. J. Statist. Mech. (2004) 2004PO6007Crossref, Google Scholar
• Braunstein A., Mézard M., Zecchina R. Survey propagation: An algorithm for satisfiability. Random Struct. Algorithms (2005) 27(2):201–226Crossref, Google Scholar
• Coughlan J. M., Ferreira S. J. Finding deformable shapes using loopy belief propagation. Eur. Conf. Comput. Vision, Vol 2352 (2002) (Springer, Berlin) 53–73Lecture Notes in Computer ScienceCrossref, Google Scholar
• Fazel M., Chiang M. Network utility maximization with nonconcave utilities using sum-of-squares method. Proc. 44th Conf. Decision Control (2005) 2(IEEE, New York) 1867–1874Crossref, Google Scholar
• Freeman W. T., Pasztor E. C., Carmichael O. T. Learning low-level vision. Internat. J. Comput. Vision (2000) 40(1):25–47Crossref, Google Scholar
• Fréville A. The multidimensional 0–1 knapsack problem: An overview. Eur. J. Oper. Res. (2004) 155(1):1–21Crossref, Google Scholar
• Frey B. J.Graphical Models for Machine Learning and Digital Communication (1998) (MIT Press, Cambridge, MA) Crossref, Google Scholar
• Gamarnik D., Nowicki T., Swirscsz G. Maximum weight independent sets and matchings in sparse random graphs: Exact results using the local weak convergence method. Random Struct. Algorithms (2005) 28(1):76–106Crossref, Google Scholar
• Hande P., Zhang S., Chiang M. Distributed rate allocation for inelastic flows. IEEE/ACM Trans. Networking (2005) 15(6):1240–1253Crossref, Google Scholar
• Kellerer H., Pferschy U., Pisinger D.Knapsack Problems (2004) (Springer, Berlin) Crossref, Google Scholar
• Kelly F. Charging and rate control for elastic traffic. Eur. Trans. Telecomm. (1997) 8(1):33–37Crossref, Google Scholar
• Lee J. W., Mazumdar R. R., Shroff N. B. Non-convex optimization and rate control for multi-class services in the Internet. IEEE/ACM Trans. Networking (2005) 13(4):841–853Crossref, Google Scholar
• Leone M., Pagnani A. Predicting protein functions with message passing algorithms. Bioinformatics (2005) 21(2):239–247Crossref, Google Scholar
• Letovsky S., Kasif S. Predicting protein function from protein/protein interaction data: A probabilistic approach. Bioinformatics (2003) 19(Supplement 1):i197–i204Crossref, Google Scholar
• Malioutov D. M., Johnson J. K., Willsky A. S. Walk-sums and belief propagation in Gaussian graphical models. J. Machine Learn. Res. (2006) 7(December):2031–2064Google Scholar
• Maneva E. N., Mossel E., Wainwright M. J. A new look at survey propagation and its generalizations. Proc. 16th Annual ACM-SIAM Sympos. Discrete Algorithms (2005) Philadelphia:1089–1098Society for Industrial and Applied MathematicsGoogle Scholar
• McCallum A., Meek C., Kjærulff U. Efficiently inducing features of conditional random fields. Proc. 19th Conf. Uncertainty Artificial Intelligence (2003) (Morgan Kaufmann, San Francisco) 403–410Google Scholar
• Mézard M., Parisi G., Zecchina R. Analytic and algorithmic solution of random satisfiability problems. Science (2002) 297(5582):812–815Crossref, Google Scholar
• Moallemi C. C., Van Roy B. Consensus propagation. IEEE Trans. Inform. Theory (2006) 52(11):4753–4766Crossref, Google Scholar
• Moallemi C. C., Van Roy B. Convergence of the min-sum algorithm for convex optimization. (2007) . Technical report, Management Science and Engineering Department, Stanford University, Stanford, CAGoogle Scholar
• Moallemi C. C., Van Roy B. Convergence of min-sum message passing for quadratic optimization. IEEE Trans. Inform. Theory (2009) 55(5):2413–2423Crossref, Google Scholar
• Montanari A., Tse D. Analysis of belief propagation for non-linear problems: The example of CDMA (or: How to prove Tanaka's formula). Proc. IEEE Inform. Theory Workshop, Punta del Este, Uruguay (2006) 160–164Crossref, Google Scholar
• Montanari A., Prabhakar B., Tse D. Belief propagation based multi-user detection. Proc. 43rd Allerton Conf. Comm. Control Comput. (2005) Monticello, ILGoogle Scholar
• Mordukhovich B. S. Nonlinear prices in nonconvex economies with classical Pareto and strong Pareto optimal allocations. Positivity (2005) 9(3):541–568Crossref, Google Scholar
• Pinto D., McCallum A., Wei X., Croft W. B. Table extraction using conditional random fields. Proc. 26th Annual Internat. ACM SIGIR Conf. Res., Dev. Inform. (2003) (ACM, New York) 235–242Crossref, Google Scholar
• Richardson T., Urbanke R., Marcus B., Rosenthal J. An introduction to the analysis of iterative coding systems. Codes, Systems, and Graphical Models. (2001a) (Springer, New York) 1–37IMA Volume in Mathmatics and Its ApplicationsCrossref, Google Scholar
• Richardson T., Urbanke R. The capacity of low-density parity check codes under message-passing decoding. IEEE Trans. Inform. Theory (2001b) 47(2):599–618Crossref, Google Scholar
• Rockafellar R. T.Convex Analysis (1970) (Princeton University Press, Princeton, NJ) Crossref, Google Scholar
• Rockafeller R. T. Augmented Lagrange multiplier functions and duality in nonconvex programming. SIAM J. Control (1974) 12(2):268–285Crossref, Google Scholar
• Rusmevichientong P., Van Roy B. An analysis of belief propagation on the turbo decoding graph with Gaussian densities. IEEE Trans. Inform. Theory (2001) 47(2):745–765Crossref, Google Scholar
• Shenker S. Fundamental design issues for the future Internet. IEEE J. Selected Areas Comm. (1995) 13(7):1176–1188Crossref, Google Scholar
• Spence M. Nonlinear prices and welfare. J. Public Econom. (1977) 8(1):1–18Crossref, Google Scholar
• Sun J., Shum H.-Y., Zheng N.-N. Stereo matching using belief propagation. Eur. Conf. Comput. Vision (ECCV 2002), Vol 2351 (2002) (Springer, Berlin) 450–452Lecture Notes in Computer ScienceCrossref, Google Scholar
• Sutton C. A., Rohanimanesh K., McCallum A. Dynamic conditional random fields: Factorized probabilistic models for labeling and segmenting sequence data. Proc. 21st Internat. Conf. Machine Learn. ACM Internat. Conf. Proc. Ser. (2004) 69(ACM, New York) 99Crossref, Google Scholar
• Talagrand M.Spin Glasses: A Challenge for Mathematicians: Cavity and Mean Field Models. (2003) 46(Springer, Berlin) . Ergebnisse der Mathematik und ihrer GrenzgebieteGoogle Scholar
• Tatikonda S. C., Jordan M. I., Darwiche A., Friedman N. Loopy belief propagation and Gibbs measures. Proc. 18th Conf. Uncertainty in Artificial Intelligence (2002) (Morgan Kaufmann, San Francisco) 493–500Google Scholar
• Wainwright M. J., Jaakkola T., Willsky A. S. Tree consistency and bounds on the performance of the max-product algorithm and its generalizations. Statist. Comput. (2004) 14(2):143–166Crossref, Google Scholar
• Weiss Y., Freeman W. T. Correctness of belief propagation in Gaussian graphical models of arbitrary topology. Neural Comput. (2001a) 13(10):2173–2200Crossref, Google Scholar
• Weiss Y., Freeman W. T. On the optimality of solutions of the max-product belief propagation algorithm in arbitrary graphs. IEEE Trans. Inform. Theory (2001b) 47(2):736–744Crossref, Google Scholar