点击次数：

论文类型：期刊论文

发表时间：2015-01-11

发表刊物：THEORETICAL COMPUTER SCIENCE

收录刊物：SCIE、EI

卷号：562

期号：C

页面范围：395-405

ISSN号：0304-3975

关键字：Online algorithm; Competitive analysis; Randomized algorithm; Knapsack problem

摘要：In this paper, we study online knapsack problems. The input is a sequence of items e(1), e(2), ..., e(n), each of which has a size and a value. Given the ith item e(i), we either put ei into the knapsack or reject it. In the removable setting, when ei is put into the knapsack, some items in the knapsack are removed with no cost if the sum of the size of ei and the total size 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 present a simple randomized 2-competitive algorithm for the unweighted non-removable case and show that it is the best possible, where knapsack problem is called unweighted if the value of each item is equal to its size. For the removable case, we propose a randomized 2-competitive algorithm despite there is no constant competitive deterministic algorithm. We also provide a lower bound 1 + 1/e approximate to 1.368 for the competitive ratio. For the unweighted removable case, we propose a 10/7-competitive algorithm and provide a lower bound 1.25 for the competitive ratio. (C) 2014 Elsevier B.V. All rights reserved.