Approximation algorithm for the 2-stage stochastic matroid base problem

DOI10.1016/J.ORL.2022.01.004MaRDI QIDQ2670486zbMATH OpenOpenAlexFDO

Authors Takuro Fukunaga, R. Ravi, Oleksandr Rudenko, Ziye Tang

Publication date 11 March 2022

Published in Operations Research Letters (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

Full work available at URL https://doi.org/10.1016/j.orl.2022.01.004

zbMATH Keywords

greedy algorithmsubmodular set covertwo-stage stochastic matroid base problem

Mathematics Subject Classification ID

Operations research, mathematical programming (90-XX)

Recommendations

• A factor \(\frac {1}{2}\) approximation algorithm for two-stage stochastic matching problems
• scientific article; zbMATH DE number 1086990
• Sampling and cost-sharing: approximation algorithms for stochastic optimization problems
• Hedging uncertainty: approximation algorithms for stochastic optimization problems
• Boosted sampling

Cites work

• An analysis of the greedy algorithm for the submodular set covering problem
• List coloring of matroids and base exchange properties
• On Two-Stage Stochastic Minimum Spanning Trees

This page was built for publication: Approximation algorithm for the 2-stage stochastic matroid base problem

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