Research map / Bandits and online learning / Online convex optimization and games
Augmenting Online Algorithms for Knapsack Problem with Total Weight Information
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.
Augments the online knapsack problem with exact or predicted total weight information, proposing KWA (competitive ratio W(e^{-1}(U-L)/L)+1), a learning-augmented PWA with consistency/robustness trade-offs, and LWA for total weight below twice capacity.
Problem
The classical online knapsack problem ignores total weight information, which is often known or predictable in practice, leaving the optimal ln(U/L)+1 competitive ratio unimproved.
Approach
A threshold function that does not depend on remaining total weight, combined with a fill-up rule that accepts all remaining items when they fit, yields a Lambert-W competitive ratio; a learning-augmented mix of this algorithm and classical OKA uses a predicted total weight with a tunable trade-off parameter.
Key results
- KWA achieves competitive ratio W(e^{-1}(U-L)/L)+1 with exact total weight, proven optimal and tight, improving on ln(U/L)+1.
- PWA is c2/(1-λ)-robust and c1c2/(λc2+(1-λ)c1)-consistent, where c1 is the KWA ratio and c2=ln(U/L)+1.
- LWA attains competitive ratio strictly below ln(U/L)+1 when 1<W<2 (ratio in (1, ln(U/L)+1)); ratio 1 when W≤1.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use exact total weight with KWA | Online knapsack · Exact total weight | competitive ratio: ln(U/L) + 1 -> W( 1/e (U−L)/L ) + 1 | Helped |
| Use predicted total weight and split capacity between KWA and OKA | Online knapsack · Arbitrary prediction error | competitive ratio: c2/(1−λ) robust; c1c2/(λc2+(1−λ)c1) consistent | Mixed |
| Use predicted total weight with PWA | Online knapsack · Prediction error η ≥ 0 | competitive ratio: c1(η)c2/(λc2 + (1 − λ)c1(η)) | Hurt |
| Use known total weight with LWA when W ≤ 1 | Online knapsack · W ≤ 1 | competitive ratio: 1 | Helped |
| Use known total weight with LWA when 1 < W < 2 | Online knapsack · 1 < W < 2 | competitive ratio: θ2 ∈ (1, ln(U/L) + 1) | Helped |
| Use known total weight with LWA when W ≥ 2 | Online knapsack · W ≥ 2 | competitive ratio: ln(U/L) + 1 | No clear effect |
| Remove KWA's fill-up logic (ablation) | KWA · Exact total weight | competitive ratio: W( 1/e (U−L)/L ) + 1 -> ln(U/L) + 1 | Hurt |
| Vary λ to allocate capacity between KWA and OKA (ablation) | PWA · Predicted total weight | robustness: c2/(1−λ) | Mixed |
Surprising findings
- Knowing total weight does not require the threshold to depend on remaining total weight; a threshold independent of it is still optimal.
Limitations
- Analysis assumes small item weights relative to capacity (infinitesimal weights).
- LWA competitive ratio in the 1<W<2 regime has no closed form and is given only numerically.
- No empirical experiments reported; results are purely theoretical.
Experimental setup
Metrics: competitive ratio consistency robustness
Baselines: OKA (classical optimal online knapsack algorithm)
Builds on: online knapsack threshold algorithm (OKA) learning-augmented online algorithms (consistency and robustness) El-Yaniv one-way trading with known deadline
Closest papers by meaning
- Online Knapsack with Frequency Predictions (NeurIPS 2021 · similarity 0.90)
- Near-Optimal Consistency-Robustness Trade-Offs for Learning-Augmented Online Knapsack Problems (ICML 2025 · similarity 0.89)
- Time Fairness in Online Knapsack Problems (ICLR 2024 · similarity 0.87)
- Bandits with Replenishable Knapsacks: the Best of both Worlds (ICLR 2024 · similarity 0.84)
- Beyond Primal-Dual Methods in Bandits with Stochastic and Adversarial Constraints (NeurIPS 2024 · similarity 0.83)
- Learning-Augmented Algorithms for $k$-median via Online Learning (NeurIPS 2025 · similarity 0.82)
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.