Indexed by:期刊论文

Date of Publication:2010-10-25

Journal:THEORETICAL COMPUTER SCIENCE

Included Journals:SCIE、EI、Scopus

Volume:411

Issue:44-46

Page Number:3956-3964

ISSN No.:0304-3975

Key Words:Knapsack problem; Online algorithms; Competitive ratio

Abstract: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.