Near-Optimal Consistency-Robustness Trade-Offs for Learning-Augmented Online Knapsack Problems

Mohammadreza Daneshvaramoli, Helia Karisani, Adam Lechowicz, Bo Sun, Cameron N Musco, Mohammad Hajiesmaili
Proceedings of the 42nd International Conference on Machine Learning, PMLR 267:12459-12489, 2025.

Abstract

This paper introduces a family of learning-augmented algorithms for online knapsack problems that achieve near Pareto-optimal consistency-robustness trade-offs through a simple combination of trusted learning-augmented and worst-case algorithms. Our approach relies on succinct, practical predictions—single values or intervals estimating the minimum value of any item in an offline solution. Additionally, we propose a novel fractional-to-integral conversion procedure, offering new insights for online algorithm design.

Cite this Paper

BibTeX
@InProceedings{pmlr-v267-daneshvaramoli25a, title = {Near-Optimal Consistency-Robustness Trade-Offs for Learning-Augmented Online Knapsack Problems}, author = {Daneshvaramoli, Mohammadreza and Karisani, Helia and Lechowicz, Adam and Sun, Bo and Musco, Cameron N and Hajiesmaili, Mohammad}, booktitle = {Proceedings of the 42nd International Conference on Machine Learning}, pages = {12459--12489}, year = {2025}, editor = {Singh, Aarti and Fazel, Maryam and Hsu, Daniel and Lacoste-Julien, Simon and Berkenkamp, Felix and Maharaj, Tegan and Wagstaff, Kiri and Zhu, Jerry}, volume = {267}, series = {Proceedings of Machine Learning Research}, month = {13--19 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v267/main/assets/daneshvaramoli25a/daneshvaramoli25a.pdf}, url = {https://proceedings.mlr.press/v267/daneshvaramoli25a.html}, abstract = {This paper introduces a family of learning-augmented algorithms for online knapsack problems that achieve near Pareto-optimal consistency-robustness trade-offs through a simple combination of trusted learning-augmented and worst-case algorithms. Our approach relies on succinct, practical predictions—single values or intervals estimating the minimum value of any item in an offline solution. Additionally, we propose a novel fractional-to-integral conversion procedure, offering new insights for online algorithm design.} }
Endnote
%0 Conference Paper %T Near-Optimal Consistency-Robustness Trade-Offs for Learning-Augmented Online Knapsack Problems %A Mohammadreza Daneshvaramoli %A Helia Karisani %A Adam Lechowicz %A Bo Sun %A Cameron N Musco %A Mohammad Hajiesmaili %B Proceedings of the 42nd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2025 %E Aarti Singh %E Maryam Fazel %E Daniel Hsu %E Simon Lacoste-Julien %E Felix Berkenkamp %E Tegan Maharaj %E Kiri Wagstaff %E Jerry Zhu %F pmlr-v267-daneshvaramoli25a %I PMLR %P 12459--12489 %U https://proceedings.mlr.press/v267/daneshvaramoli25a.html %V 267 %X This paper introduces a family of learning-augmented algorithms for online knapsack problems that achieve near Pareto-optimal consistency-robustness trade-offs through a simple combination of trusted learning-augmented and worst-case algorithms. Our approach relies on succinct, practical predictions—single values or intervals estimating the minimum value of any item in an offline solution. Additionally, we propose a novel fractional-to-integral conversion procedure, offering new insights for online algorithm design.
APA
Daneshvaramoli, M., Karisani, H., Lechowicz, A., Sun, B., Musco, C.N. & Hajiesmaili, M.. (2025). Near-Optimal Consistency-Robustness Trade-Offs for Learning-Augmented Online Knapsack Problems. Proceedings of the 42nd International Conference on Machine Learning, in Proceedings of Machine Learning Research 267:12459-12489 Available from https://proceedings.mlr.press/v267/daneshvaramoli25a.html.

Related Material