Anzeige
Erschienen in:
2013 | OriginalPaper | Buchkapitel
Randomized Algorithms for Removable Online Knapsack Problems
verfasst von : Xin Han, Yasushi Kawase, Kazuhisa Makino
Erschienen in: Frontiers in Algorithmics and Algorithmic Aspects in Information and Management
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
In this paper, we study removable online knapsack problem. The input is a sequence of items
e
1
,
e
2
,…,
e
n
, each of which has a weight and a value. Given the
i
th item
e
i
, we either put
e
i
into the knapsack or reject it. When
e
i
is put into the knapsack, some items in the knapsack are removed with no cost if the sum of the weight of
e
i
and the total weight in the current knapsack exceeds the capacity of the knapsack. Our goal is to maximize the profit, i.e., the sum of the values of items in the last knapsack. We show a randomized 2-competitive algorithm despite there is no constant competitive deterministic algorithm. We also give a lower bound 1 + 1/
e
≈ 1.368. For the unweighted case, i.e., the value of each item is equal to the weight, we propose a 10/7-competitive algorithm and give a lower bound 1.25.