| Title: |
Stealing from the Dragon’s Hoard: Online Unbounded Knapsack With Removal |
| Authors: |
Gehnen, Matthias; Stocker, Moritz |
| Contributors: |
Matthias Gehnen and Moritz Stocker |
| Publisher Information: |
Schloss Dagstuhl – Leibniz-Zentrum für Informatik |
| Publication Year: |
2026 |
| Collection: |
DROPS - Dagstuhl Research Online Publication Server (Schloss Dagstuhl - Leibniz Center for Informatics ) |
| Subject Terms: |
online problems; online knapsack; unbounded knapsack; removal |
| Description: |
We introduce the Online Unbounded Knapsack Problem with Removal, a variation of the well-known Online Knapsack Problem. Items, each with a weight and value, arrive online and an algorithm must decide on whether or not to pack them into a knapsack with a fixed weight limit. An item may be packed an arbitrary number of times and items may be removed from the knapsack at any time without cost. The goal is to maximize the total value of items packed, while respecting a weight limit. We show that this is one of the very few natural online knapsack variants that allow for competitive deterministic algorithms in the general setting, by providing an algorithm with competitivity 1.6911. We complement this with a lower bound of 1.5877. We also analyze the proportional setting, where the weight and value of any single item agree, and show that deterministic algorithms can be exactly 3/2-competitive. Lastly, we give lower and upper bounds of 6/5 and 4/3 on the competitivity of randomized algorithms in this setting. |
| Document Type: |
article in journal/newspaper; conference object |
| File Description: |
application/pdf |
| Language: |
English |
| Relation: |
Is Part Of LIPIcs, Volume 364, 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026); https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2026.43 |
| DOI: |
10.4230/LIPIcs.STACS.2026.43 |
| Availability: |
https://doi.org/10.4230/LIPIcs.STACS.2026.43; https://nbn-resolving.org/urn:nbn:de:0030-drops-255327; https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2026.43 |
| Rights: |
https://creativecommons.org/licenses/by/4.0/legalcode |
| Accession Number: |
edsbas.ED94B64A |
| Database: |
BASE |