Two-stage stochastic matching and spanning tree problems: Polynomial instances and approximation
Gourvès, Laurent; Escoffier, Bruno; Spanjaard, Olivier; Monnot, Jérôme (2010), Two-stage stochastic matching and spanning tree problems: Polynomial instances and approximation, European Journal of Operational Research, 205, 1, p. 19-30. http://dx.doi.org/10.1016/j.ejor.2009.12.004
TypeArticle accepté pour publication ou publié
Journal nameEuropean Journal of Operational Research
MetadataShow full item record
Abstract (EN)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 [N. Kong, A.J. Schaefer, A factor 1/2 approximation algorithm for two-stage stochastic matching problems, European Journal of Operational Research 172(3) (2006) 740–746]. They have proved that the problem is NP-hard, and they have provided a factor View the MathML source 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.
Subjects / KeywordsStochastic programming; Approximation algorithms; Matching; Maximum spanning tree; Combinatorial optimization
Showing items related by title and author.
Complexity and Approximation Results for the Connected Vertex Cover Problem in Graphs and Hypergraphs Monnot, Jérôme; Gourvès, Laurent; Escoffier, Bruno (2010) Article accepté pour publication ou publié