Near-Optimal Consistency-Robustness Trade-Offs for Learning-Augmented Online Knapsack Problems
This work addresses optimization challenges in resource allocation for scenarios like cloud computing, though it is incremental as it builds on existing learning-augmented frameworks.
The paper tackles the online knapsack problem by developing learning-augmented algorithms that achieve near Pareto-optimal trade-offs between consistency and robustness, using simple predictions like single values or intervals to estimate item values in offline solutions.
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.