利用追索权与规模上界求解可移除物品的在线背包问题
Leveraging Recourse and Size Bounds for OnlineKnapsack with Removable Items
Dimitris Fotakis, Laurent Gourvès, Aris Pagourtzis, Panagiotis Patsilinakos
AI 速览：该论文研究在线无权重背包问题，在允许移除已接受物品的基础上，结合物品规模上界知识与有限追索权（重新插入曾被拒物品），给出竞争比的紧界并提出自适应在线算法。
In the online unweighted knapsack problem, items arrive sequentially and must be accepted or rejected immediately for a bounded-capacity knapsack, aiming to maximize the total size of accepted items. When decisions are irrevocable, no algorithm achieves a non-trivial competitive ratio. An essential relaxation that circumvents this impossibility is to allow previously accepted items to be removed from the knapsack (a.k.a. removal). In this work, we investigate possible further improvements on the competitive ratio with removal by bringing together two other previously proposed model extensions: knowledge of an upper bound on the item sizes (a.k.a. bound awareness) and ability to reinsert previously rejected items(a.k.a.recourse). Our contributions are twofold. First, we establish close upper and lower bounds on the competitive ratio under bound awareness, removal and recourse. We show that significant improvements on the best known competitive ratio are possible when the upper bound on the item sizes is not too restrictive and only few uses of recourse are available. Second, we introduce the notion of adaptive online algorithms which do not require to know any upper bound on the item sizes but still achieve performance guarantees comparable to the ones obtained under the bound awareness model.