Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
438233 | Theoretical Computer Science | 2014 | 8 Pages |
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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Xin Han, Yasushi Kawase, Kazuhisa Makino, He Guo,