Near-Optimal Consistency-Robustness Trade-Offs for Learning-Augmented Online Knapsack Problems
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908441254035456 |
|---|---|
| author | Daneshvaramoli, Mohammadreza Karisani, Helia Lechowicz, Adam Sun, Bo Musco, Cameron Hajiesmaili, Mohammad |
| author_facet | Daneshvaramoli, Mohammadreza Karisani, Helia Lechowicz, Adam Sun, Bo Musco, Cameron Hajiesmaili, Mohammad |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2406_18752 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Near-Optimal Consistency-Robustness Trade-Offs for Learning-Augmented Online Knapsack Problems Daneshvaramoli, Mohammadreza Karisani, Helia Lechowicz, Adam Sun, Bo Musco, Cameron Hajiesmaili, Mohammad Machine Learning Computer Science and Game Theory 68Q25, 68T05 F.2.2; I.2.6 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. |
| title | Near-Optimal Consistency-Robustness Trade-Offs for Learning-Augmented Online Knapsack Problems |
| topic | Machine Learning Computer Science and Game Theory 68Q25, 68T05 F.2.2; I.2.6 |
| url | https://arxiv.org/abs/2406.18752 |