Online removable knapsack problem under convex function ?
In this paper, we address an online knapsack problem under a convex sizeprofit 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 + 5 ) / 2 -competitive, which is optimal. Finally, we prove that the lower bound of this problem is ( 1 + 5 ) / 2 .
knapsack problems online algorithms competitive ratio