Online Unit Profit Knapsack with Predictions
Open Access
- 13 June 2024
- journal article
- research article
- Published by Springer Nature in Algorithmica
- Vol. 86 (9) , 2786-2821
Abstract
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=\frac{a}{\hat{a}}$$ where a is the actual value for this average size and $$\hat{a}$$ is the prediction. We give an algorithm which is $$\frac{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 $$\frac{e-1}{e}r$$ , if $$r \le 1$$ , and $$\frac{e-r}{e}r$$ , if $$1 \le 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 $$\frac{1}{2r}$$ for $$r\ge 1$$ and $$\frac{r}{2}$$ for $$r\le 1$$ . We show that improving the result for any $$r< 1$$ leads to a worse result for some $$r>1$$ .
Keywords
All Related Versions
Funding Information
- University of Southern Denmark
This publication has 32 references indexed in Scilit:
- Online search with a hintInformation and Computation, 2023
- Online Interval Scheduling with Predictions2023
- Secretary and online matching problems with machine learned adviceDiscrete Optimization, 2023
- Online Bin Packing with Advice of Small SizeTheory of Computing Systems, 2018
- An Introduction to Online Computation2016
- Online Knapsack RevisitedTheory of Computing Systems, 2014
- The online knapsack problem: Advice and randomizationTheoretical Computer Science, 2014
- Budget Constrained Bidding in Keyword Auctions and Online Knapsack Problems2008
- Knapsack Problems2004
- Stochastic on-line knapsack problemsMathematical Programming, 1995