点击次数：

论文类型：期刊论文

发表时间：2019-09-27

发表刊物：THEORETICAL COMPUTER SCIENCE

收录刊物：SCIE、EI

卷号：786

页面范围：88-95

ISSN号：0304-3975

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

摘要：In this paper, we address an online knapsack problem under concave function f(x), i.e., an item with size x has its profit f (x). We first obtain a simple lower bound max{q, f'(0)/f(1)}, where holden ratio q approximate to 1.618, then show that this bound is not tight, and give an improved lower bound. Finally, we find the online algorithm for linear function can be employed to the concave case, and prove its competitive ratio is f'(0)/f(1/q), then we give a refined online algorithm with a competitive ratio f'(0)/f(1) + 1 when f'(0)/f(1) is very large. And we also give optimal algorithms for some specific piecewise linear functions. (C) 2018 Elsevier B.V. All rights reserved.