Anzeige
Erschienen in:
2010 | OriginalPaper | Buchkapitel
Online Minimization Knapsack Problem
verfasst von : Xin Han, Kazuhisa Makino
Erschienen in: Approximation and Online Algorithms
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 address the online minimization knapsack problem, i. e., the items are given one by one over time and the goal is to minimize the total cost of items that covers a knapsack. We study the
removable
model, where it is allowed to remove old items from the knapsack in order to accept a new item. We obtain the following results.
1
We propose an 8-competitive deterministic and memoryless algorithm for the problem, which contrasts to the result for the online maximization knapsack problem that no online algorithm has a bounded competitive ratio [8].
2
We propose a 2e-competitive randomized algorithm for the problem.
3
We derive a lower bound 2 for deterministic algorithms for the problem.
4
We propose a 1.618-competitive deterministic algorithm for the case in which each item has its size equal to its cost, and show that this is best possible.