Home > Research > Publications & Outputs > Time-constrained restless bandits and the knaps...

Research

Associated organisational unit

Electronic data

  • cs06

    Rights statement: The final, definitive version of this article has been published in the Journal, Electronic Notes in Discrete Mathematics 28, 2007, © ELSEVIER.

    Accepted author manuscript, 147 KB, PDF document

Links

Text available via DOI:

Keywords

View graph of relations

Time-constrained restless bandits and the knapsack problem for perishable items (Extended Abstract)

Research output: Contribution to Journal/Magazine › Journal article

Published
Close
More...
<mark>Journal publication date</mark>1/03/2007
<mark>Journal</mark>Electronic Notes in Discrete Mathematics
Volume28
Number of pages8
Pages (from-to)145-152
Publication StatusPublished
<mark>Original language</mark>English

Abstract

Motivated by a food promotion problem, we introduce the Knapsack Problem for Perishable Items (KPPI) to address a dynamic problem of optimally filling a knapsack with items that disappear randomly. The KPPI naturally bridges the gap and elucidates the relation between the PSPACE-hard restless bandit problem and the NP-hard knapsack problem. Our main result is a problem decomposition method resulting in an approximate transformation of the KPPI into an associated 0-1 knapsack problem. The approach is based on calculating explicitly the marginal productivity indices in a generic finite-horizon restless bandit subproblem.

Bibliographic note

The final, definitive version of this article has been published in the Journal, Electronic Notes in Discrete Mathematics 28, 2007, © ELSEVIER.