ICML 2025poster0 citations
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
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.
Learning AugmentedSuccinct Predictions
BibTeX
@inproceedings{
daneshvaramoli2025nearoptimal,
title={Near-Optimal Consistency-Robustness Trade-Offs for Learning-Augmented Online Knapsack Problems},
author={Mohammadreza Daneshvaramoli and Helia Karisani and Adam Lechowicz and Bo Sun and Cameron N Musco and Mohammad Hajiesmaili},
booktitle={Forty-second International Conference on Machine Learning},
year={2025},
url={https://openreview.net/forum?id=AhumZOmTDf}
}