Approximating the Stochastic Knapsack Problem: The Benefit of Adaptivity
From MaRDI portal
Publication:3169009
DOI10.1287/moor.1080.0330zbMath1218.90169OpenAlexW2041025394WikidataQ101124186 ScholiaQ101124186MaRDI QIDQ3169009
Michel X. Goemans, Jan Vondrák, Brian C. Dean
Publication date: 27 April 2011
Published in: Mathematics of Operations Research (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1287/moor.1080.0330
Stochastic programming (90C15) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Approximation algorithms (68W25)
Related Items (63)
Packing a Knapsack of Unknown Capacity ⋮ Approximation algorithms for stochastic combinatorial optimization problems ⋮ Improved Approximation Algorithms for Stochastic Matching ⋮ Polymatroid Prophet Inequalities ⋮ Ignorant vs. Anonymous Recommendations ⋮ Exact algorithms for the 0-1 time-bomb knapsack problem ⋮ Unrelated Machine Scheduling with Stochastic Processing Times ⋮ Submodular Stochastic Probing on Matroids ⋮ Column generation strategies and decomposition approaches for the two-stage stochastic multiple knapsack problem ⋮ A shortest-path-based approach for the stochastic knapsack problem with non-decreasing expected overfilling costs ⋮ Non-adaptive stochastic score classification and explainable halfspace evaluation ⋮ Stochastic Knapsack Revisited: The Service Level Perspective ⋮ The Risk-Averse Static Stochastic Knapsack Problem ⋮ Adaptivity in the stochastic blackjack knapsack problem ⋮ Configuration balancing for stochastic requests ⋮ Stochastic packing integer programs with few queries ⋮ Prioritized interdiction of nuclear smuggling via tabu search ⋮ On the adaptivity gap of stochastic orienteering ⋮ Turnpikes in Finite Markov Decision Processes and Random Walk ⋮ Stochastic graph exploration with limited resources ⋮ Adaptivity gaps for the stochastic Boolean function evaluation problem ⋮ Approximation Algorithms for Stochastic and Risk-Averse Optimization ⋮ The stochastic generalized bin packing problem ⋮ Stochastic Probing with Increasing Precision ⋮ Robust execution strategies for project scheduling with unreliable resources and stochastic durations ⋮ Toward a model for backtracking and dynamic programming ⋮ Logarithmic Regret in the Dynamic and Stochastic Knapsack Problem with Equal Rewards ⋮ An adversarial model for scheduling with testing ⋮ Approximations to Stochastic Dynamic Programs via Information Relaxation Duality ⋮ Ignorance Is Almost Bliss: Near-Optimal Stochastic Matching with Few Queries ⋮ Adaptive Submodular Ranking and Routing ⋮ The benefit of adaptivity in the stochastic knapsack problem with dependence on the state of nature ⋮ Randomized algorithms for online knapsack problems ⋮ The benefit of adaptivity in stochastic packing problems with probing ⋮ Stochastic Unsplittable Flows ⋮ Lower bounds on the adaptivity gaps in variants of the stochastic knapsack problem ⋮ Relaxation Analysis for the Dynamic Knapsack Problem with Stochastic Item Sizes ⋮ Unnamed Item ⋮ A column and constraint generation algorithm for the dynamic knapsack problem with stochastic item sizes ⋮ Improved bounds in stochastic matching and optimization ⋮ When LP is the cure for your matching woes: improved bounds for stochastic matchings ⋮ A PTAS for the chance-constrained knapsack problem with random item sizes ⋮ Stochastic set packing problem ⋮ Maximizing expected utility over a knapsack constraint ⋮ Queue-constrained packing: a vehicle ferry case study ⋮ Optimal composition ordering problems for piecewise linear functions ⋮ Upper bounds for the 0-1 stochastic knapsack problem and a B\&B algorithm ⋮ On competitive recommendations ⋮ Improvements and Generalizations of Stochastic Knapsack and Markovian Bandits Approximation Algorithms ⋮ Maximizing Expected Utility for Stochastic Combinatorial Optimization Problems ⋮ Semi-Infinite Relaxations for the Dynamic Knapsack Problem with Stochastic Item Sizes ⋮ Stochastic graph exploration ⋮ Submodular Maximization with Uncertain Knapsack Capacity ⋮ Stage-\(t\) scenario dominance for risk-averse multi-stage stochastic mixed-integer programs ⋮ Unnamed Item ⋮ Running Errands in Time: Approximation Algorithms for Stochastic Orienteering ⋮ Improved online algorithm for fractional knapsack in the random order model ⋮ A Tight 2-Approximation for Preemptive Stochastic Scheduling ⋮ Strongly polynomial FPTASes for monotone dynamic programs ⋮ Dynamic node packing ⋮ Narrowing the search for optimal call-admission policies via a nonlinear stochastic knapsack model ⋮ Unnamed Item ⋮ Adaptive Bin Packing with Overflow
This page was built for publication: Approximating the Stochastic Knapsack Problem: The Benefit of Adaptivity
