2014年6月
Online removable knapsack problem under convex function
THEORETICAL COMPUTER SCIENCE
- ,
- ,
- ,
- 巻
- 540
- 号
- 開始ページ
- 62
- 終了ページ
- 69
- 記述言語
- 英語
- 掲載種別
- 研究論文(学術雑誌)
- DOI
- 10.1016/j.tcs.2013.09.013
- 出版者・発行元
- ELSEVIER SCIENCE BV
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 + root 5)/2-competitive, which is optimal. Finally, we prove that the lower bound of this problem is (1 + root 5)/2. (C) 2013 Elsevier B.V. All rights reserved.
- リンク情報
- ID情報
-
- DOI : 10.1016/j.tcs.2013.09.013
- ISSN : 0304-3975
- eISSN : 1879-2294
- Web of Science ID : WOS:000338598800007