Research map / Bandits and online learning / Online convex optimization and games
Near-Optimal Consistency-Robustness Trade-Offs for Learning-Augmented Online Knapsack Problems
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes learning-augmented online knapsack algorithms (PP-a, IPA, MIX, Fr2Int) using succinct point or interval predictions of the critical value, achieving near Pareto-optimal consistency-robustness trade-offs.
Problem
Online knapsack problems (fractional and integral) lack Pareto-optimal consistency-robustness trade-offs under learning-augmented settings, and existing prediction models (frequency predictions) are complex and impractical.
Approach
Use a single point or interval prediction of the critical value (minimum value of items admitted by the offline optimum). A reserve-while-greedy algorithm (PP-a) adaptively adjusts reserved capacity with prebuying reaches 1+min{1,ŵ}; MIX mixes a prediction-based algorithm with the worst-case threshold algorithm ZCL; a value-partitioning conversion (Fr2Int) transfers fractional results to integral
Key results
- PP-a achieves the best average and worst-case empirical competitive ratio among prediction-based algorithms on 2,000 synthetic OFKP instances, with PP-n better on average than others but worse worst-case than ZCL.
- Theory: point-prediction PP-a is (1+min{1,ŵ})-competitive, matching a lower bound; IPA is (2+ln(u/ℓ))-competitive, matching a lower bound.
- MIX is (c/λ)-consistent and ((ln(U/L)+1)/(1-λ))-robust, nearly matching the lower bound Ω((1+ln(U/L))/(1-λ)) for 2/λ-consistent algorithms.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Replace PP-b's fixed reservation with PP-a's adaptive reserve-while-greedy strategy | OFKP with a trusted point prediction · OFKP, trusted point prediction | competitive ratio: 2 to 1+\min\{1,\hat{\omega}\} | Helped |
| Use a point prediction of the critical value with PP-a | OFKP · 2,000 synthetic OFKP instances | empirical competitive ratio | Helped |
| Use a naive point-prediction rule that accepts items at or above the predicted critical value | OFKP · 2,000 synthetic OFKP instances | worst-case empirical competitive ratio | Hurt |
| Use IPA with interval predictions | OFKP · 2,000 synthetic OFKP instances | empirical competitive ratio | Helped |
| Vary the value ratio U/L while using a trusted succinct prediction | PP-b, PP-a, and IPA · Synthetic instances with varying U/L | empirical competitive ratio | Helped |
| Decrease the critical-value weight ω̂ | PP-a · Synthetic instances with ω̂ varied over 0.29, 0.45, 0.63, and 0.78 | empirical competitive ratio | Helped |
| Use interval prediction instead of no prediction | IPA versus ZCL · Synthetic instances with varying U/L | empirical competitive ratio | Helped |
Surprising findings
- A naive greedy point-prediction algorithm (PP-n) outperforms most others on average but has worse worst-case performance than the prediction-free ZCL.
Limitations
- Integral results rely on small item weight and bounded value assumptions.
- Robustness guarantees require known value bounds L and U.
- Lower bounds for consistency-robustness trade-off are asymptotic (U/L to infinity) and gap remains due to constants.
Experimental setup
Datasets: synthetic power-law instances Bitcoin price data Google cluster traces
Benchmarks: synthetic OFKP instances Bitcoin price data Google cluster traces
Metrics: empirical competitive ratio worst-case competitive ratio consistency robustness
Baselines: ZCL PP-n PP-b IPA SENTINEL
Builds on: ZCL threshold algorithm learning-augmented consistency-robustness framework SENTINEL frequency-prediction algorithm advice complexity of online knapsack
Closest papers by meaning
- Augmenting Online Algorithms for Knapsack Problem with Total Weight Information (AAAI 2025 · similarity 0.89)
- Learning-Augmented Online Bidding in Stochastic Settings (NeurIPS 2025 · similarity 0.86)
- Time Fairness in Online Knapsack Problems (ICLR 2024 · similarity 0.86)
- Overcoming Brittleness in Pareto-Optimal Learning Augmented Algorithms (NeurIPS 2024 · similarity 0.85)
- Bandits with Replenishable Knapsacks: the Best of both Worlds (ICLR 2024 · similarity 0.83)
- Learning-Augmented Algorithms for $k$-median via Online Learning (NeurIPS 2025 · similarity 0.83)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.