Two-stage stochastic matching and spanning tree problems: Polynomial instances and approximation

Two-stage stochastic matching and spanning tree problems: Polynomial instances and approximation

0.00 Avg rating0 Votes
Article ID: iaor20101875
Volume: 205
Issue: 1
Start Page Number: 19
End Page Number: 30
Publication Date: Aug 2010
Journal: European Journal of Operational Research
Authors: , , ,
Keywords: matching, minimum spanning trees
Abstract:

This article deals with the two-stage stochastic model, which aims at explicitly taking into account uncertainty in optimization problems, that Kong and Schaefer have recently studied for the maximum weight matching problem (2006). They have proved that the problem is NP-hard, and they have provided a factor ½ approximation algorithm. We further study this problem and strengthen the hardness results, slightly improve the approximation ratio and exhibit some polynomial cases. We similarly tackle the maximum weight spanning tree problem in the two-stage setting. Finally, we make numerical experiments on randomly generated instances to compare the quality of several interesting heuristics.

Reviews

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