Online knapsack algorithms improve with item removal and size knowledge
Leveraging Recourse and Size Bounds for OnlineKnapsack with Removable Items
Data Structures and AlgorithmsComputation and Language
Summary
The online knapsack problem involves deciding immediately whether to accept items of varying sizes into a limited space, aiming to use the space most efficiently. Traditionally, once an item is accepted, it cannot be removed, making it very hard to perform well. The authors study a scenario where removing previously accepted items and reinserting rejected ones is allowed, combined with knowing an upper limit on item sizes or adapting without this knowledge. They find that these relaxations lead to better algorithms that get closer to the best possible performance.
What this means in practice
- •For cloud resource allocators: Improve dynamic allocation of limited resources by using algorithms that allow adjusting accepted tasks based on known size constraints and limited reversals.
- •For inventory management teams: Manage storage space more efficiently by allowing selective removal and reinsertion of items with knowledge or adaptation to item size limits.
Authors
Dimitris Fotakis, Laurent Gourvès, Aris Pagourtzis, Panagiotis Patsilinakos
Abstract
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.