2026-08-21T18:34:57Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27433 2026-08-21T14:42:39Z ddc:004 open_access

Improved Results for Knapsack with Removal Gehnen, Matthias Güven, Kübra Hächler, Valentin Komm, Dennis Královič, Richard Online computation competitive analysis knapsack problem predictions We study the proportional online knapsack problem with removal. For randomized algorithms, we tighten the gap between the current lower and upper bounds on the expected competitive ratio by presenting a lower bound of roughly 1.27. We further study this problem under the model of online algorithms with predictions. Our lower bound arguments are agnostic to the type of available prediction, which makes them very general. For deterministic algorithms, we provide a tightly matching upper bound on the competitive ratio for a specific kind of weight prediction. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Matthias Gehnen and Kübra Güven and Valentin Hächler and Dennis Komm and Richard Královič 2026 Is Part Of LIPIcs, Volume 386, 51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2026.51 urn:nbn:de:0030-drops-274331 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2026.51 eng https://creativecommons.org/licenses/by/4.0/legalcode