点击次数：

论文类型：期刊论文

发表时间：2014-06-26

发表刊物：THEORETICAL COMPUTER SCIENCE

收录刊物：SCIE、EI、Scopus

卷号：540

期号：,SI

页面范围：62-69

ISSN号：0304-3975

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

摘要：In this paper, we address an online knapsack problem under a convex size profit function. We first give a greedy online algorithm with a competitive ratio 2. Then we propose an improved online algorithm with a competitive ratio 5/3. We also prove that when the convex function has a specific property, our improved online algorithm is (1 + root 5)/2-competitive, which is optimal. Finally, we prove that the lower bound of this problem is (1 + root 5)/2. (C) 2013 Elsevier B.V. All rights reserved.