DROPS

Document

DOI: 10.4230/LIPIcs.MFCS.2026.51

Improved Results for Knapsack with Removal

Authors: Matthias Gehnen, Kübra Güven, Valentin Hächler, Dennis Komm, and Richard Královič

Published in: LIPIcs, Volume 386, 51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026)

Abstract

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.

Cite as

Matthias Gehnen, Kübra Güven, Valentin Hächler, Dennis Komm, and Richard Královič. Improved Results for Knapsack with Removal. In 51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 386, pp. 51:1-51:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{gehnen_et_al:LIPIcs.MFCS.2026.51,
  author =	{Gehnen, Matthias and G\"{u}ven, K\"{u}bra and H\"{a}chler, Valentin and Komm, Dennis and Kr\'{a}lovi\v{c}, Richard},
  title =	{{Improved Results for Knapsack with Removal}},
  booktitle =	{51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026)},
  pages =	{51:1--51:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-442-0},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{386},
  editor =	{Kouck\'{y}, Michal and Petrișan, Daniela},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2026.51},
  URN =		{urn:nbn:de:0030-drops-274331},
  doi =		{10.4230/LIPIcs.MFCS.2026.51},
  annote =	{Keywords: Online computation, competitive analysis, knapsack problem, predictions}
}

Search Results

Documents authored by Güven, Kübra

Improved Results for Knapsack with Removal

Abstract

Cite as

Thanks for your feedback!

Could not send message