Online Simple Knapsack with Reservation Costs

arXiv (Cornell University)

Abstract

In the online simple knapsack problem items are presented in an iterative fashion and an algorithm has to decide for each item whether to reject or permanently include it into the knapsack without any knowledge about the rest of the instance. The goal is to pack the knapsack as full as possible. In this work, we introduce the option of reserving items for the cost of a fixed fraction $α$ of their size. An algorithm may pay this fraction in order to postpone its decision on whether to include or reject these items until after the last item of the instance was presented. While the classical online simple knapsack problem does not admit any constantly bounded competitive ratio in the deterministic setting, we find that adding the possibility of reservation makes the problem constantly competitive. We give tight bounds for the whole range of $α$ from $0$ to $1$.

Authors 5

1. Hans-Joachim Boeckenhauer

   ETH Zurich

   Affiliation as printed

   ETH Zürich

2. Elisabet Burjons Aachen

   ETH Zurich · RWTH Aachen University

   Affiliation as printed

   Department of Computer Science , ETH Zürich , Universitätstrasse 6 , 8092 Zürich , Switzerland

   RWTH Aachen University

3. Juraj Hromkovic̆ Aachen

   ETH Zurich · RWTH Aachen University

   Affiliation as printed

   Department of Computer Science , ETH Zürich , Universitätstrasse 6 , 8092 Zürich , Switzerland

   RWTH Aachen University

4. Henri Lotze Aachen Department of Computer Science

   RWTH Aachen University

   Affiliation as printed

   Department of Computer Science , RWTH Aachen University , Ahornstrasse 55 , 52074 Aachen , Germany

   RWTH Aachen University

5. Peter Rossmanith Aachen Department of Computer Science

   RWTH Aachen University

   Affiliation as printed

   Department of Computer Science , RWTH Aachen University , Ahornstrasse 55 , 52074 Aachen , Germany