Browsing Stochastic Programming E-print Series (SPEPS) by Subject "Matching"
Now showing items 1-1 of 1
2004-02-19BuchA factor 1/2 approximation algorithm for a class of two-stage stochastic mixed-integer programs Abstract We introduce the two-stage stochastic maximum-weight matching problem and demonstrate that this problem is NP-complete. We give a factor 1/2 approximation algorithm and prove its correctness. We also provide a ...