# Online Unit Profit Knapsack with Untrusted Predictions

**Authors:** Joan Boyar, Lene M. Favrholdt, Kim S. Larsen  
**arXiv:** [2203.00285](https://arxiv.org/abs/2203.00285)  
**Date:** 2022-03-01  
**Summary page:** https://www.summarizepaper.com/en/paper/2203.00285v1/

## Key points

- The paper studies the online knapsack problem in the context of trusted and untrusted predictions.
- They consider a variant of the problem where items have unit profit, known as Unit Profit Knapsack.
- It is easy to find an optimal solution offline by packing as many of the smallest items as possible into the knapsack.
- For Online Unit Profit Knapsack, where predictions may be obtained from a machine learning source, the competitive ratio is unbounded.
- The authors propose an algorithm that uses the prediction error ratio $r=\frac{a}{\hat{a}}$ to achieve a competitive ratio of $\frac{1}{2r}$ for $r\geq 1$ and $\frac{r}{2}$ for $r\leq 1$.
- Using an adversary technique, they demonstrate that this result is optimal in some sense, providing a trade-off in attainable competitive ratios for different values of $r$.
- While their result for accurate advice ($r=1$) yields only a competitive ratio of $\frac{1}{2}$, no algorithm knowing the value $a$ can achieve a better competitive ratio than $\frac{e-1}{e}\approx 0.6321$.
- They present an algorithm with a matching upper bound which attains a competitive ratio of $r\frac{e-1}{e}$ for $r \leq 1$ and $\frac{e-r}{e}$ for $1 \leq r < e$, and show that no algorithm can be better for both cases when $r<1$ or when $1\leq r<e$.
- Overall, this paper provides a thorough analysis of the online knapsack problem in the context of trusted and untrusted predictions. It proposes algorithms with provable competitive ratios and demonstrates optimality results.

## Summary

The paper "Online Unit Profit Knapsack with Untrusted Predictions" presents a study of the online knapsack problem in the context of trusted and untrusted predictions. The authors consider a variant of the problem where items have unit profit, known as Unit Profit Knapsack, and show that it is easy to find an optimal solution offline by packing as many of the smallest items as possible into the knapsack. However, for Online Unit Profit Knapsack, where predictions may be obtained from a machine learning source, the competitive ratio is unbounded. Previous work on online algorithms with untrusted predictions generally studied problems where an online algorithm with a constant competitive ratio is known. In this paper, the authors propose an algorithm that uses the prediction error ratio $r=\frac{a}{\hat{a}}$, where $a$ is the actual value for the average size of those smallest items that fit in the knapsack and $\hat{a}$ is the prediction. The presented algorithm achieves a competitive ratio of $\frac{1}{2r}$ for $r\geq 1$ and $\frac{r}{2}$ for $r\leq 1$. Using an adversary technique, they demonstrate that this result is optimal in some sense, providing a trade-off in attainable competitive ratios for different values of $r$. The authors note that while their result for accurate advice ($r=1$) yields only a competitive ratio of $\frac{1}{2}$, no algorithm knowing the value $a$ can achieve a better competitive ratio than $\frac{e-1}{e}\approx 0.6321$. They present an algorithm with a matching upper bound which attains a competitive ratio of $r\frac{e-1}{e}$ for $r \leq 1$ and $\frac{e-r}{e}$ for $1 \leq r < e$, and show that no algorithm can be better for both cases when $r<1$ or when $1\leq r<e$. Overall, this paper provides a thorough analysis of the online knapsack problem in the context of trusted and untrusted predictions. It proposes algorithms with provable competitive ratios and demonstrates optimality results.