License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2023.29
URN: urn:nbn:de:0030-drops-185635
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18563/
Burjons, Elisabet ;
Gehnen, Matthias ;
Lotze, Henri ;
Mock, Daniel ;
Rossmanith, Peter
The Online Simple Knapsack Problem with Reservation and Removability
Abstract
In the online simple knapsack problem, a knapsack of unit size 1 is given and an algorithm is tasked to fill it using a set of items that are revealed one after another. Each item must be accepted or rejected at the time they are presented, and these decisions are irrevocable. No prior knowledge about the set and sequence of items is given. The goal is then to maximize the sum of the sizes of all packed items compared to an optimal packing of all items of the sequence.
In this paper, we combine two existing variants of the problem that each extend the range of possible actions for a newly presented item by a new option. The first is removability, in which an item that was previously packed into the knapsack may be finally discarded at any point. The second is reservations, which allows the algorithm to delay the decision on accepting or rejecting a new item indefinitely for a proportional fee relative to the size of the given item.
If both removability and reservations are permitted, we show that the competitive ratio of the online simple knapsack problem rises depending on the relative reservation costs. As soon as any nonzero fee has to be paid for a reservation, no online algorithm can be better than 1.5-competitive. With rising reservation costs, this competitive ratio increases up to the golden ratio (ϕ ≈ 1.618) that is reached for relative reservation costs of 1-√5/3 ≈ 0.254. We provide a matching upper and lower bound for relative reservation costs up to this value. From this point onward, the tight bound by Iwama and Taketomi for the removable knapsack problem is the best possible competitive ratio, not using any reservations.
BibTeX - Entry
@InProceedings{burjons_et_al:LIPIcs.MFCS.2023.29,
author = {Burjons, Elisabet and Gehnen, Matthias and Lotze, Henri and Mock, Daniel and Rossmanith, Peter},
title = {{The Online Simple Knapsack Problem with Reservation and Removability}},
booktitle = {48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)},
pages = {29:1--29:12},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-292-1},
ISSN = {1868-8969},
year = {2023},
volume = {272},
editor = {Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/18563},
URN = {urn:nbn:de:0030-drops-185635},
doi = {10.4230/LIPIcs.MFCS.2023.29},
annote = {Keywords: online algorithm, knapsack, competitive ratio, reservation, preemption}
}
|
Keywords: |
|
online algorithm, knapsack, competitive ratio, reservation, preemption |
|
Collection: |
|
48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023) |
|
Issue Date: |
|
2023 |
|
Date of publication: |
|
21.08.2023 |
