Online knapsack with removal and recourse
Journal of Computer and System Sciences, vol. 155, pp. 103697
Abstract
We analyze the competitive ratio of the proportional online knapsack problem with removal and limited recourse. In contrast to the classical online knapsack problem, packed items can be removed and a limited number of removed items can be re-inserted to the knapsack. The variant with removal only was analyzed by Iwama and Taketomi (ICALP, 2002). We show that even a single use of recourse can improve the performance of an algorithm. We give lower bounds for a constant number of k ≥ 1 uses of recourse in total, matching upper bounds for 1 ≤ k ≤ 3 , and a general upper bound for any value of k . For a variant where a constant number of k ≥ 1 uses of recourse can be used per step, we give tight bounds for all k ≥ 1 . We further look at a scenario where an algorithm is informed when the instance ends and give improved upper bounds in both variants for this case.
Authors 6
-
Affiliation as printed
Department of Computer Science, ETH Zurich, Universitätsstrasse 6, 8092 Zurich, Switzerland
-
Centre National de la Recherche Scientifique · Université de Bordeaux · Laboratoire Bordelais de Recherche en Informatique
Affiliation as printed
CNRS, LaBRI, Université de Bordeaux, 351, cours de la Libération, 33405 Talence CEDEX, France
-
Affiliation as printed
Institute of Computer Science, University of Augsburg, Universitätsstraße 6a, 86159 Augsburg, Germany
-
Affiliation as printed
Departement of Computer Science, RWTH Aachen University, Ahornstraße 55, 52056 Aachen, Germany
-
Moritz Stocker corresponding
Affiliation as printed
Department of Computer Science, ETH Zurich, Universitätsstrasse 6, 8092 Zurich, Switzerland
-
Affiliation as printed
Department of Computer Science, ETH Zurich, Universitätsstrasse 6, 8092 Zurich, Switzerland
Cited by 1 stored of 1
1 result
No patents citing this paper on Lens.org (checked 2026-10-06).