The benefit of adaptivity in stochastic packing problems with probing

DOI10.1016/J.TCS.2014.10.032MaRDI QIDQ476898zbMATH OpenOpenAlexFDO

Authors Asaf Levin, Aleksander Vainer

Publication date 2 December 2014

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2014.10.032

zbMATH Keywords

stochastic optimizationpacking integer programsbenefit of adaptivity

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Stochastic programming (90C15)

Recommendations

• Approximating the stochastic Knapsack problem: the benefit of adaptivity
• Adaptivity and approximation for stochastic packing problems
• Lower bounds on the adaptivity gaps in variants of the stochastic knapsack problem
• The benefit of adaptivity in the stochastic knapsack problem with dependence on the state of nature
• Algorithms and adaptivity gaps for stochastic probing

Cites work

• Adaptivity and approximation for stochastic packing problems
• Approximating the stochastic Knapsack problem: the benefit of adaptivity
• Approximation Algorithms for Correlated Knapsacks and Non-martingale Bandits
• How to probe for an extreme value
• Model-driven optimization using adaptive probes

Cited in

(6)

• The benefit of adaptivity in the stochastic knapsack problem with dependence on the state of nature
• Adaptivity and approximation for stochastic packing problems
• Adaptive uncertainty resolution in Bayesian combinatorial optimization problems
• Stochastic packing integer programs with few queries
• Algorithms and adaptivity gaps for stochastic probing
• Stochastic packing integer programs with few queries

This page was built for publication: The benefit of adaptivity in stochastic packing problems with probing

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