In the online knapsack problem, the goal is to pack items arriving online
with different values and weights into a capacity-limited knapsack to maximize
the total value of the accepted items. We study \textit{learning-augmented}
algorithms for this problem, which aim to use machine-learned predictions to
move beyond pessimistic worst-case guarantees. Existing learning-augmented
algorithms for online knapsack consider relatively complicated prediction
models that give an algorithm substantial information about the input, such as
the total weight of items at each value. In practice, such predictions can be
error-sensitive and difficult to learn. Motivated by this limitation, we
introduce a family of learning-augmented algorithms for online knapsack that
use \emph{succinct predictions}. In particular, the machine-learned prediction
given to the algorithm is just a single value or interval that estimates the
minimum value of any item accepted by an offline optimal solution. By
leveraging a relaxation to online \emph{fractional} knapsack, we design
algorithms that can leverage such succinct predictions in both the trusted
setting (i.e., with perfect prediction) and the untrusted setting, where we
prove that a simple meta-algorithm achieves a nearly optimal
consistency-robustness trade-off. Empirically, we show that our algorithms
significantly outperform baselines that do not use predictions and often
outperform algorithms based on more complex prediction models.

在线背包问题的学习增强算法通过使用简洁的预测信息，在无传递完美预测和有限完美预测两种情况下，设计了能够提高算法性能的算法，并在实验中表现优于基线和复杂预测模型的算法。