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.STACS.2021.16
URN: urn:nbn:de:0030-drops-136613
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/13661/
Böckenhauer, Hans-Joachim ;
Burjons, Elisabet ;
Hromkovič, Juraj ;
Lotze, Henri ;
Rossmanith, Peter
Online Simple Knapsack with Reservation Costs
Abstract
In the Online Simple Knapsack Problem we are given a knapsack of unit size 1. Items of size smaller or equal to 1 are presented in an iterative fashion and an algorithm has to decide whether to permanently reject or include each item into the knapsack without any knowledge about the rest of the instance. The goal is then to pack the knapsack as full as possible. In this work, we introduce a third option additional to those of packing and rejecting an item, namely that of reserving an item for the cost of a fixed fraction α of its size. An algorithm may pay this fraction in order to postpone its decision on whether to include or reject the item until after the last item of the instance was presented.
While the classical Online Simple Knapsack Problem does not admit any constantly bounded competitive ratio in the deterministic setting, we find that adding the possibility of reservation makes the problem constantly competitive, with varying competitive ratios depending on the value of α. We give upper and lower bounds for the whole range of reservation costs, with tight bounds for costs up to 1/6 - an area that is strictly 2-competitive - , for costs between √2-1 and 1 - an area that is strictly (2+α)-competitive up to ϕ -1, and strictly 1/(1-α)-competitive above ϕ-1, where ϕ is the golden ratio.
With our analysis, we find a counterintuitive characteristic of the problem: Intuitively, one would expect that the possibility of rejecting items becomes more and more helpful for an online algorithm with growing reservation costs. However, for higher reservation costs above √2-1, an algorithm that is unable to reject any items tightly matches the lower bound and is thus the best possible. On the other hand, for any positive reservation cost smaller than 1/6, any algorithm that is unable to reject any items performs considerably worse than one that is able to reject.
BibTeX - Entry
@InProceedings{bockenhauer_et_al:LIPIcs.STACS.2021.16,
author = {B\"{o}ckenhauer, Hans-Joachim and Burjons, Elisabet and Hromkovi\v{c}, Juraj and Lotze, Henri and Rossmanith, Peter},
title = {{Online Simple Knapsack with Reservation Costs}},
booktitle = {38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)},
pages = {16:1--16:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-180-1},
ISSN = {1868-8969},
year = {2021},
volume = {187},
editor = {Bl\"{a}ser, Markus and Monmege, Benjamin},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/13661},
URN = {urn:nbn:de:0030-drops-136613},
doi = {10.4230/LIPIcs.STACS.2021.16},
annote = {Keywords: Online problem, Simple knapsack, Reservation costs}
}
|
Keywords: |
|
Online problem, Simple knapsack, Reservation costs |
|
Collection: |
|
38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021) |
|
Issue Date: |
|
2021 |
|
Date of publication: |
|
10.03.2021 |
