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

DOI10.1016/j.ejor.2009.12.004zbMath1187.90208MaRDI QIDQ2270290

Jérôme Monnot, Laurent Gourvès, Bruno Escoffier, Olivier Spanjaard

Publication date: 18 March 2010

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ejor.2009.12.004

zbMATH Keywords

maximum spanning tree

Mathematics Subject Classification ID

90C15: Stochastic programming

90C59: Approximation methods and heuristics in mathematical programming

90C27: Combinatorial optimization

Related Items

On greedy approximation algorithms for a class of two-stage stochastic assignment problems, On the approximability of robust spanning tree problems, Approximability of the two-stage stochastic knapsack problem with discretely distributed weights

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Optimization, approximation, and complexity classes
• Some simplified NP-complete graph problems
• A factor \(\frac {1}{2}\) approximation algorithm for two-stage stochastic matching problems
• Hedging uncertainty: approximation algorithms for stochastic optimization problems
• On the random 2-stage minimum spanning tree
• Boosted sampling
• Introduction to Stochastic Programming
• Commitment Under Uncertainty: Two-Stage Stochastic Matching Problems
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques