Online Unit Profit Knapsack with Untrusted Predictions.

Joan Boyar, Lene M. Favrholdt, and Kim S. Larsen.
Algorithmica. Accepted for publication.

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.

---

other publications

Other publications by the author.