Online Knapsack with Frequency Predictions
Sungjin Im, Ravi Kumar, Mahshid Montazer Qaem, Manish Purohit
Abstract
There has been recent interest in using machine-learned predictions to improve the worst-case guarantees of online algorithms. In this paper we continue this line of work by studying the online knapsack problem, but with very weak predictions: in the form of knowing an upper and lower bound for the number of items of each value. We systematically derive online algorithms that attain the best possible competitive ratio for any fixed prediction; we also extend the results to more general settings such as generalized one-way trading and two-stage online knapsack. Our work shows that even seemingly weak predictions can be utilized effectively to provably improve the performance of online algorithms.
BibTeX
@inproceedings{
im2021online,
title={Online Knapsack with Frequency Predictions},
author={Sungjin Im and Ravi Kumar and Mahshid Montazer Qaem and Manish Purohit},
booktitle={Advances in Neural Information Processing Systems},
editor={A. Beygelzimer and Y. Dauphin and P. Liang and J. Wortman Vaughan},
year={2021},
url={https://openreview.net/forum?id=1XxaUEa3Yz}
}