Running summarizing tools on a new article

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.