Two-stage stochastic matching and spanning tree problems: polynomial instances and approximation
From MaRDI portal
Publication:2270290
DOI10.1016/j.ejor.2009.12.004zbMath1187.90208MaRDI QIDQ2270290
Olivier Spanjaard, Laurent Gourvès, Jérôme Monnot, Bruno Escoffier
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
90C15: Stochastic programming
90C59: Approximation methods and heuristics in mathematical programming
90C27: Combinatorial optimization
Related Items
Analysis of Sparse Cutting Planes for Sparse MILPs with Applications to Stochastic MILPs, On greedy approximation algorithms for a class of two-stage stochastic assignment problems, On the approximability of robust spanning tree problems, Robust recoverable and two-stage selection 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