Seminari CS

Abstract

Online General Knapsack with Reservation Costs
(Elisabet Burjon Pujol, UPC)

In the online general knapsack problem, an algorithm is presented with an item x = (s, v) of size s and value v and must irrevocably choose to pack such an item into the knapsack or reject it before the next item appears. The goal is to maximize the total value of the packed items without overflowing the knapsack’s capacity. As this classical setting is way too harsh for many real-life applications,
we will analyze the online general knapsack problem under the reservation model. Here, instead of accepting or rejecting an item immediately, an algorithm can delay the decision of whether to pack the item by paying a fraction 0 ≤ α of the size or the value of the item. This models many practical applications, where, for example, decisions can be delayed for some
costs e.g. cancellation fees. We present results for both variants: First, for costs depending on the value of the items and then for costs depending on the size of the items.
If the reservation costs depend on the value of the items, we find that no algorithm is competitive for reservation costs larger than 1/2 of the item value, and we find upper and lower bounds for the rest of the reservation factor range 0 ≤ α < 1/2. On the other hand, if the reservation costs depend on the size of the items, we find a matching upper and lower bound of 2 for every reservation factor α