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

DOI10.1016/J.EJOR.2009.12.004MaRDI QIDQ2270290zbMATH OpenOpenAlexFDO

Authors Laurent Gourvès, Jérôme Monnot, Olivier Spanjaard, 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

zbMATH Keywords

maximum spanning tree

Mathematics Subject Classification ID

Stochastic programming (90C15) Combinatorial optimization (90C27) Approximation methods and heuristics in mathematical programming (90C59)

Recommendations

• A factor \(\frac {1}{2}\) approximation algorithm for two-stage stochastic matching problems
• On Two-Stage Stochastic Minimum Spanning Trees
• Commitment under uncertainty: Two-stage stochastic matching problems
• Commitment Under Uncertainty: Two-Stage Stochastic Matching Problems
• Hedging uncertainty: approximation algorithms for stochastic optimization problems

Cites work

• A factor \(\frac {1}{2}\) approximation algorithm for two-stage stochastic matching problems
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Boosted sampling
• Commitment Under Uncertainty: Two-Stage Stochastic Matching Problems
• Hedging uncertainty: approximation algorithms for stochastic optimization problems
• scientific article; zbMATH DE number 3783030 (Why is no real title available?)
• scientific article; zbMATH DE number 663895 (Why is no real title available?)
• scientific article; zbMATH DE number 6469210 (Why is no real title available?)
• Introduction to Stochastic Programming
• On the random 2-stage minimum spanning tree
• Optimization, approximation, and complexity classes
• Some simplified NP-complete graph problems

Cited in

(7)

• Robust recoverable and two-stage selection problems
• Approximability of the two-stage stochastic knapsack problem with discretely distributed weights
• A factor \(\frac {1}{2}\) approximation algorithm for two-stage stochastic matching problems
• Analysis of Sparse Cutting Planes for Sparse MILPs with Applications to Stochastic MILPs
• Commitment Under Uncertainty: Two-Stage Stochastic Matching Problems
• On greedy approximation algorithms for a class of two-stage stochastic assignment problems
• On the approximability of robust spanning tree problems

This page was built for publication: Two-stage stochastic matching and spanning tree problems: polynomial instances and approximation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2270290)