Online Unit Profit Knapsack with Untrusted Predictions.

Joan Boyar, Lene M. Favrholdt, and Kim S. Larsen.
Algorithmica, 86: 2786-2821, 2024.

A variant of the online knapsack problem is considered in the setting of predictions. In Unit Profit Knapsack, the items have unit profit, i.e., the goal is to pack as many items as possible. For Online Unit Profit Knapsack, the competitive ratio is unbounded. In contrast, it is easy to find an optimal solution offline: Pack as many of the smallest items as possible into the knapsack. The prediction available to the online algorithm is the average size of those smallest items that fit in the knapsack. For the prediction error in this hard online problem, we use the ratio r = a/â where a is the actual value for this average size and â is the prediction. We give an algorithm which is (e-1)/e-competitive, if r = 1, and this is best possible among online algorithms knowing a and nothing else. More generally, the algorithm has a competitive ratio of r(e-1)/e, if r ≤ 1, and r(e-r)/e, if 1 ≤ r < e. Any algorithm with a better competitive ratio for some r < 1 will have a worse competitive ratio for some r > 1. To obtain a positive competitive ratio for all r, we adjust the algorithm, resulting in a competitive ratio of 1/(2r) for r ≥ 1 and r/2 for r ≤ 1. We show that improving the result for any r < 1 leads to a worse result for some r > 1.

---

publication

Link to the publication at the publisher's site - subscription may be required.
Text required by the publisher (if any): The final publication is available at link.springer.com.

open access (487 KB)

The same as the publisher's version, when the publisher permits. Otherwise, the author's last version before the publisher's copyright; this is often exactly the same, but sometimes fonts, page numbers, figure numbers, etc. are different. It may also be a full version. However, it is safe to read this version, and at the same time cite the official version, as long as references to concrete locations, numbered theorems, etc. inside the article are avoided.

other publications

Other publications by the author.