Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
482678 | European Journal of Operational Research | 2006 | 7 Pages |
Abstract
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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computer Science (General)
Authors
Nan Kong, Andrew J. Schaefer,