Online simple knapsack with bounded predictions

DOI10.4230/LIPICS.STACS.2024.37MaRDI QIDQ6902685zbMATH OpenFDO

Authors Matthias Gehnen, Henri Lotze, Peter Rossmanith

Publication date 10 November 2025

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.STACS.2024.37

zbMATH Keywords

machine-learned adviceonline problempredictionssimple knapsack

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• Distortion-oblivious algorithms for scheduling on multiple machines
• Exact solution of the robust knapsack problem
• Flow time scheduling with uncertain processing time
• scientific article; zbMATH DE number 1232130 (Why is no real title available?)
• scientific article; zbMATH DE number 2086630 (Why is no real title available?)
• scientific article; zbMATH DE number 7650261 (Why is no real title available?)
• k-Means Has Polynomial Smoothed Complexity
• Learning-augmented algorithms for online subset sum
• Learning-augmented query policies for minimum spanning tree with uncertainty
• Online knapsack with resource augmentation
• Online removable knapsack with limited cuts
• Online Scheduling via Learned Weights
• Online unit profit knapsack with untrusted predictions
• Random knapsack in expected polynomial time
• Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time
• Stochastic on-line knapsack problems
• Strategyproof scheduling with predictions
• The online knapsack problem with incremental capacity
• The online knapsack problem: advice and randomization

Cited in

(3)

• Online general knapsack with reservation costs
• A survey of online knapsack problems
• Online knapsack problems with estimates

This page was built for publication: Online simple knapsack with bounded predictions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6902685)