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

Mohammadreza Daneshvaramoli, Helia Karisani, Adam Lechowicz, Bo Sun, Cameron Musco +1 more
6/26/2024
cs.LGcs.GT

No official code found. Best implementation: moreda-a/OKP (0 stars, last commit 2025-01-31).

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.

View on arXivView PDF

Code Implementations(1)

moreda-a/OKPCommunity100%
00C++, MATLABMay 22, 20241 years ago

Similar Papers

Time Fairness in Online Knapsack Problems

84% match1 repo2023

Overcoming Brittleness in Pareto-Optimal Learning-Augmented Algorithms

83% match2024

A Simple Learning-Augmented Algorithm for Online Packing with Concave Objectives

83% match2024

On Tradeoffs in Learning-Augmented Algorithms

81% match2025

Learning-Augmented Algorithms for Online Concave Packing and Convex Covering Problems

80% match2024

Learning-Augmented Online Bipartite Fractional Matching

79% match2025

Cite this paper

@article{daneshvaramoli2024nearoptimal,
  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 Musco and Mohammad Hajiesmaili},
  year   = {2024},
  eprint = {2406.18752},
  archivePrefix = {arXiv},
  url    = {http://arxiv.org/abs/2406.18752v2},
  journal = {ICML 2024 2024}
}

Add a badge to your README

Shows whether official code is linked for this paper.

Code of Paper badge
[![Code of Paper](https://codeofpaper.com/badge/2406.18752.svg)](https://codeofpaper.com/paper/2406.18752)

Discussion