Time-Constrained Restless Bandits and the Knapsack Problem for Perishable Items (Extended Abstract) |
| |
Institution: | 1. Fluminense Federal University Niterói, RJ, Brazil;2. Federal Rural University of Pernambuco Garanhuns, PE, Brazil;3. Federal University of Paraíba João Pessoa, PB, Brazil |
| |
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: | |
本文献已被 ScienceDirect 等数据库收录! |
|