Randomized Algorithms for Online Knapsack Problems

• Item type: SIG Technical Reports(1)
• 公開日: 2013-10-30
• タイトル: Randomized Algorithms for Online Knapsack Problems
• タイトル / 言語: en
• タイトル: Randomized Algorithms for Online Knapsack Problems
• 言語: eng
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: Software School, Dalian University of Technology
• 著者所属: University of Tokyo
• 著者所属: Kyoto University
• 著者所属(英): en
• 著者所属(英): Software School, Dalian University of Technology
• 著者所属(英): en
• 著者所属(英): University of Tokyo
• 著者所属(英): en
• 著者所属(英): Kyoto University
• 著者名: Xin, Han; Yasushi, Kawase; Kazuhisa, Makino
• 著者名(英): Xin, Han; Yasushi, Kawase; Kazuhisa, Makino
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: In this paper, we study online knapsack problems. The input is a sequence of items e1, e2,..., en, each of which has a size and a value. Given the ith item ei, we either put ei into the knapsack or reject it. In the removable setting, when ei is put into the knapsack, some items in the knapsack are removed with no cost if the sum of the size of ei and the total size in the current knapsack exceeds the capacity of the knapsack. Our goal is to maximize the profit, i.e., the sum of the values of items in the last knapsack. We present a simple randomized 2-competitive algorithm for the unweighted non-removable case and show that it is the best possible, where knapsack problem is called unweighted if the value of each item is equal to its size. For the removable case, we propose a randomized 2-competitive algorithm despite there is no constant competitive deterministic algorithm. We also provide a lower bound 1+1/e ≒ 1.368 for the competitive ratio. For the unweighted removable case, we propose a 10/7-competitive algorithm and provide a lower bound 1.25 for the competitive ratio.
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: In this paper, we study online knapsack problems. The input is a sequence of items e1, e2,..., en, each of which has a size and a value. Given the ith item ei, we either put ei into the knapsack or reject it. In the removable setting, when ei is put into the knapsack, some items in the knapsack are removed with no cost if the sum of the size of ei and the total size in the current knapsack exceeds the capacity of the knapsack. Our goal is to maximize the profit, i.e., the sum of the values of items in the last knapsack. We present a simple randomized 2-competitive algorithm for the unweighted non-removable case and show that it is the best possible, where knapsack problem is called unweighted if the value of each item is equal to its size. For the removable case, we propose a randomized 2-competitive algorithm despite there is no constant competitive deterministic algorithm. We also provide a lower bound 1+1/e ≒ 1.368 for the competitive ratio. For the unweighted removable case, we propose a 10/7-competitive algorithm and provide a lower bound 1.25 for the competitive ratio.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 研究報告アルゴリズム（AL）; 巻 2013-AL-145, 号 8, p. 1-8, 発行日 2013-10-30
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会