تقرير
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 |
|---|