点击次数：

论文类型：期刊论文

发表时间：2010-10-25

发表刊物：THEORETICAL COMPUTER SCIENCE

收录刊物：SCIE、EI、Scopus

卷号：411

期号：44-46

页面范围：3956-3964

ISSN号：0304-3975

关键字：Knapsack problem; Online algorithms; Competitive ratio

摘要：In this paper, we study online maximization and minimization knapsack problems with limited cuts, in which (1) items are given one by one over time, i.e., after a decision is made on the current item, the next one is given, (2) items are allowed to be cut at most k (>= 1) times, and (3) items are allowed to be removed from the knapsack.
   We obtain the following three results.
   (i) For the maximization knapsack problem, we propose a (k + 1)/k-competitive online algorithm, and show that it is the best possible, i.e., no online algorithm can have a competitive ratio less than (k 1)/k.
   (ii) For the minimization knapsack problem, we show that no online algorithm can have a constant competitive ratio.
   (iii) We extend the result in (i) to the resource augmentation model, where an online algorithm is allowed to use a knapsack of capacity m (>1), while the optimal algorithm uses a unit capacity knapsack. (C) 2010 Elsevier B.V. All rights reserved.