点击次数：

论文类型：期刊论文

发表时间：2016-01-04

发表刊物：THEORETICAL COMPUTER SCIENCE

收录刊物：SCIE、EI、Scopus

卷号：609

页面范围：185-196

ISSN号：0304-3975

关键字：Knapsack; Competitive analysis; Online algorithms

摘要：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.
   (i) We propose a 8-competitive deterministic and memoryless algorithm for the problem, which contrasts with the result for the online maximization knapsack problem that no online algorithm has a bounded competitive ratio [14].
   (ii) We propose a 2e-competitive randomized algorithm for the problem.
   (iii) We derive a lower bound of 2 for deterministic algorithms for the problem.
   (iv) We propose a 1.618-competitive deterministic algorithm for the case in which each item has size equal to its cost, and show that this is best possible. (C) 2015 Elsevier B.V. All rights reserved.