Improved Results for Knapsack with Removal
DROPS (Schloss Dagstuhl – Leibniz Center for Informatics)
Abstract
We study the proportional online knapsack problem with removal. For randomized algorithms, we tighten the gap between the current lower and upper bounds on the expected competitive ratio by presenting a lower bound of roughly 1.27. We further study this problem under the model of online algorithms with predictions. Our lower bound arguments are agnostic to the type of available prediction, which makes them very general. For deterministic algorithms, we provide a tightly matching upper bound on the competitive ratio for a specific kind of weight prediction.
Authors 4
-
Affiliation as printed
Department of Computer Science, RWTH Aachen University, Germany
-
Affiliation as printed
Department of Computer Science, ETH Zurich, Switzerland
-
Affiliation as printed
Department of Computer Science, ETH Zurich, Switzerland
-
Affiliation as printed
Department of Computer Science, ETH Zurich, Switzerland
Cited by 0 stored of 0
No patents citing this paper on Lens.org (checked 2026-10-06).