تقرير
Stochastic optimization by message passing
العنوان: | Stochastic optimization by message passing |
---|---|
المؤلفون: | Altarelli, Fabrizio, Braunstein, Alfredo, Ramezanpour, Abolfazl, Zecchina, Riccardo |
المصدر: | J. Stat. Mech. (2011) P11009 |
سنة النشر: | 2011 |
المجموعة: | Computer Science Condensed Matter |
مصطلحات موضوعية: | Condensed Matter - Statistical Mechanics, Computer Science - Distributed, Parallel, and Cluster Computing, Computer Science - Data Structures and Algorithms |
الوصف: | Most optimization problems in applied sciences realistically involve uncertainty in the parameters defining the cost function, of which only statistical information is known beforehand. In a recent work we introduced a message passing algorithm based on the cavity method of statistical physics to solve the two-stage matching problem with independently distributed stochastic parameters. In this paper we provide an in-depth explanation of the general method and caveats, show the details of the derivation and resulting algorithm for the matching problem and apply it to a stochastic version of the independent set problem, which is a computationally hard and relevant problem in communication networks. We compare the results with some greedy algorithms and briefly discuss the extension to more complicated stochastic multi-stage problems. Comment: 31 pages, 8 figures |
نوع الوثيقة: | Working Paper |
DOI: | 10.1088/1742-5468/2011/11/P11009 |
URL الوصول: | http://arxiv.org/abs/1108.6160 |
رقم الأكسشن: | edsarx.1108.6160 |
قاعدة البيانات: | arXiv |
DOI: | 10.1088/1742-5468/2011/11/P11009 |
---|