A factor ½ approximation algorithm for two-stage stochastic matching problems

A factor ½ approximation algorithm for two-stage stochastic matching problems

0.00 Avg rating0 Votes
Article ID: iaor20084041
Country: Netherlands
Volume: 172
Issue: 3
Start Page Number: 740
End Page Number: 746
Publication Date: Aug 2006
Journal: European Journal of Operational Research
Authors: ,
Keywords: heuristics, programming: probabilistic
Abstract:

We introduce the two-stage stochastic maximum-weight matching problem and demonstrate that this problem is NP-complete. We give a factor ½ approximation algorithm and prove its correctness. We also provide a tight example to show the bound given by the algorithm is exactly ½. 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.

Reviews

Required fields are marked *. Your email address will not be published.