Online removable knapsack problem under convex function

DOI Web Site Web Site 被引用文献5件 参考文献11件

説明

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 .

収録刊行物

被引用文献 (5)*注記

もっと見る

参考文献 (11)*注記

もっと見る

関連プロジェクト

もっと見る

詳細情報 詳細情報について

問題の指摘

ページトップへ