Approximating the Stochastic Knapsack Problem: The Benefit of Adaptivity
Authors:
Top Cited Papers
- 1 November 2008
- journal article
- research article
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Mathematics of Operations Research
- Vol. 33 (4) , 945-964
Abstract
We consider a stochastic variant of the NP-hard 0/1 knapsack problem, in which item values are deterministic and item sizes are independent random variables with known, arbitrary distributions. Items are placed in the knapsack sequentially, and the act of placing an item in the knapsack instantiates its size. Our goal is to compute a solution “policy” that maximizes the expected value of items successfully placed in the knapsack, where the final overflowing item contributes no value. We consider both nonadaptive policies (that designate a priori a fixed sequence of items to insert) and adaptive policies (that can make dynamic choices based on the instantiated sizes of items placed in the knapsack thus far). An important facet of our work lies in characterizing the benefit of adaptivity. For this purpose we advocate the use of a measure called the adaptivity gap: the ratio of the expected value obtained by an optimal adaptive policy to that obtained by an optimal nonadaptive policy. We bound the adaptivity gap of the stochastic knapsack problem by demonstrating a polynomial-time algorithm that computes a nonadaptive policy whose expected value approximates that of an optimal adaptive policy to within a factor of four. We also devise a polynomial-time adaptive policy that approximates the optimal adaptive policy to within a factor of 3 + ε for any constant ε > 0.Keywords
This publication has 21 references indexed in Scilit:
- Stochastic Machine Scheduling with Precedence ConstraintsSIAM Journal on Computing, 2005
- Hedging Uncertainty: Approximation Algorithms for Stochastic Optimization ProblemsLecture Notes in Computer Science, 2004
- Beyond Competitive AnalysisSIAM Journal on Computing, 2000
- Approximation in stochastic schedulingJournal of the ACM, 1999
- An algorithm for maximizing target achievement in the stochastic knapsack problem with normal returnsNaval Research Logistics (NRL), 1993
- On the optimality of LEPT and cµ rules for machines in parallelJournal of Applied Probability, 1992
- Scheduling stochastic jobs with due dates on parallel machinesEuropean Journal of Operational Research, 1990
- Preference Order Stochastic Knapsack Problems: Methodological IssuesJournal of the Operational Research Society, 1980
- A Preference Order Dynamic Program for a Knapsack Problem with Stochastic RewardsJournal of the Operational Research Society, 1979
- Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey1979