Lower bounds on the adaptivity gaps in variants of the stochastic knapsack problem

DOI10.1007/s10878-017-0234-xzbMath1395.90215OpenAlexW2773002526MaRDI QIDQ1743485

Aleksander Vainer, Asaf Levin

Publication date: 13 April 2018

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-017-0234-x

zbMATH Keywords

knapsackstochastic combinatorial optimizationbenefit of adaptivity

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• An adaptive stochastic knapsack problem
• Adaptivity in the stochastic blackjack knapsack problem
• Stochastic models for budget optimization in search-based advertising
• A PTAS for the chance-constrained knapsack problem with random item sizes
• Stochastic budget optimization in internet advertising
• The benefit of adaptivity in the stochastic knapsack problem with dependence on the state of nature
• Approximating the Stochastic Knapsack Problem: The Benefit of Adaptivity
• Stochastic Covering and Adaptivity
• The Dynamic and Stochastic Knapsack Problem with Deadlines
• Improvements and Generalizations of Stochastic Knapsack and Multi-Armed Bandit Approximation Algorithms: Extended Abstract
• Approximation Algorithms for Correlated Knapsacks and Non-martingale Bandits
• Stochastic combinatorial optimization via poisson approximation

This page was built for publication: Lower bounds on the adaptivity gaps in variants of the stochastic knapsack problem