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

Standard

Time-constrained restless bandits and the knapsack problem for perishable items (Extended Abstract). / Jacko, Peter; Niño-Mora, José.
In: Electronic Notes in Discrete Mathematics, Vol. 28, 01.03.2007, p. 145-152.

Research output: Contribution to Journal/Magazine › Journal article

Harvard

Jacko, P & Niño-Mora, J 2007, 'Time-constrained restless bandits and the knapsack problem for perishable items (Extended Abstract)', Electronic Notes in Discrete Mathematics, vol. 28, pp. 145-152. https://doi.org/10.1016/j.endm.2007.01.021

APA

Jacko, P., & Niño-Mora, J. (2007). Time-constrained restless bandits and the knapsack problem for perishable items (Extended Abstract). Electronic Notes in Discrete Mathematics, 28, 145-152. https://doi.org/10.1016/j.endm.2007.01.021

Vancouver

Jacko P, Niño-Mora J. Time-constrained restless bandits and the knapsack problem for perishable items (Extended Abstract). Electronic Notes in Discrete Mathematics. 2007 Mar 1;28:145-152. doi: 10.1016/j.endm.2007.01.021

Author

Jacko, Peter ; Niño-Mora, José. / Time-constrained restless bandits and the knapsack problem for perishable items (Extended Abstract). In: Electronic Notes in Discrete Mathematics. 2007 ; Vol. 28. pp. 145-152.

Bibtex

@article{355834159faa47839b8c18f1bea85537,
title = "Time-constrained restless bandits and the knapsack problem for perishable items (Extended Abstract)",
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.",
keywords = "knapsack problem, perishable items, restless bandits, finite horizon, index policy heuristic",
author = "Peter Jacko and Jos{\'e} Ni{\~n}o-Mora",
note = "The final, definitive version of this article has been published in the Journal, Electronic Notes in Discrete Mathematics 28, 2007, {\textcopyright} ELSEVIER.",
year = "2007",
month = mar,
day = "1",
doi = "10.1016/j.endm.2007.01.021",
language = "English",
volume = "28",
pages = "145--152",
journal = "Electronic Notes in Discrete Mathematics",
issn = "1571-0653",
publisher = "Elsevier",

}

RIS

TY - JOUR

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

AU - Jacko, Peter

AU - Niño-Mora, José

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

PY - 2007/3/1

Y1 - 2007/3/1

N2 - 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.

AB - 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.

KW - knapsack problem

KW - perishable items

KW - restless bandits

KW - finite horizon

KW - index policy heuristic

U2 - 10.1016/j.endm.2007.01.021

DO - 10.1016/j.endm.2007.01.021

M3 - Journal article

VL - 28

SP - 145

EP - 152

JO - Electronic Notes in Discrete Mathematics

JF - Electronic Notes in Discrete Mathematics

SN - 1571-0653

ER -