Online removable knapsack problem under convex function

DOI Web Site Web Site 5 Citations 11 References

Description

Abstract 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 + 5 ) / 2 -competitive, which is optimal. Finally, we prove that the lower bound of this problem is ( 1 + 5 ) / 2 .

Journal

Citations (5)*help

See more

References(11)*help

See more

Related Projects

See more

Report a problem

Back to top