Paper Info
Title
Online knapsack problem under concave functions.
Abstract
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≈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.
Year
DOI
Venue
2019
10.1016/j.tcs.2018.03.025
Theoretical Computer Science
Keywords
DocType
Volume
Online algorithms,Knapsack problems,Competitive ratio
Journal
786
ISSN
Citations 
PageRank 
0304-3975
0
0.34
References 
Authors
0
3
Name
Order
Citations
PageRank
Xin Han121324.49
Qinyang Chen200.34
Kazuhisa Makino31088102.74