Indexed by:期刊论文

Date of Publication:2015-01-11

Journal:THEORETICAL COMPUTER SCIENCE

Included Journals:SCIE、EI

Volume:562

Issue:C

Page Number:395-405

ISSN No.:0304-3975

Key Words:Online algorithm; Competitive analysis; Randomized algorithm; Knapsack problem

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