On the 2-Stage Stochastic-Weighted Matching Problem
Balabhaskar Balasundaram · 2005
We study a 2-stage stochastic extension of the classical maximum weighted matching prob-lem on graphs, proposed recently by Kong and Schaefer [2004]. The authors show the NP-hardness of the problem and present a constant factor approximation algorithm. This work explores an extension of this approximation algorithm and studies its computational perfor-mance. 1