論文

査読有り
2014年6月

Online removable knapsack problem under convex function

THEORETICAL COMPUTER SCIENCE
  • Xin Han
  • ,
  • Yasushi Kawase
  • ,
  • Kazuhisa Makino
  • ,
  • He Guo

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.

リンク情報
DOI
https://doi.org/10.1016/j.tcs.2013.09.013
Web of Science
https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcAuth=JSTA_CEL&SrcApp=J_Gate_JST&DestLinkType=FullRecord&KeyUT=WOS:000338598800007&DestApp=WOS_CPL
ID情報
  • DOI : 10.1016/j.tcs.2013.09.013
  • ISSN : 0304-3975
  • eISSN : 1879-2294
  • Web of Science ID : WOS:000338598800007

エクスポート
BibTeX RIS