کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
482678 | 1446219 | 2006 | 7 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
A factor 12 approximation algorithm for two-stage stochastic matching problems
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
علوم کامپیوتر (عمومی)
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: A factor 12 approximation algorithm for two-stage stochastic matching problems A factor 12 approximation algorithm for two-stage stochastic matching problems](/preview/png/482678.png)
چکیده انگلیسی
We introduce the two-stage stochastic maximum-weight matching problem and demonstrate that this problem is NPNP-complete. We give a factor 12 approximation algorithm and prove its correctness. We also provide a tight example to show the bound given by the algorithm is exactly 12. Computational results on some two-stage stochastic bipartite matching instances indicate that the performance of the approximation algorithm appears to be substantially better than its worst-case performance.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Operational Research - Volume 172, Issue 3, 1 August 2006, Pages 740–746
Journal: European Journal of Operational Research - Volume 172, Issue 3, 1 August 2006, Pages 740–746
نویسندگان
Nan Kong, Andrew J. Schaefer,