文献

J-GLOBAL ID：202102212969782150   整理番号：21A1430776

オンラインナップサック問題に対するアルゴリズム

著者 (1件)： 河瀬康志 (東大 大学院情報理工学系研究科)
資料名： オペレーションズ・リサーチ
巻： 66  号： 5  ページ： 293-299  発行年： 2021年05月01日 
JST資料番号： F0251A  ISSN： 0030-3674  CODEN： OPREA  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： ナップサック問題は,容量をもつナップサックが一つと,価値と重さをもつ品物の集合が与えられたとき,重さの総和が容量を超えないという制約の下で,価値の総和を最大にする品物集合を求める最適化問題である.オンラインナップサック問題とは,品物が逐次的に与えられる状況におけるナップサック問題である.本稿では,オンラインナップサック問題に対するアルゴリズムを紹介し,その性能を競合比によって議論する.(著者抄録)

シソーラス用語： *ナップサック問題 ,  *最適化 ,  オンライン処理 ,  最適化問題 ,  比率 ,  解析 ,  アルゴリズム ,  近似法 ,  *改変
準シソーラス用語： オンラインナップサック問題 ,  *オンライン最適化 ,  競合比 ,  競合比解析 ,  貪欲アルゴリズム

分類 (1件)： その他のオペレーションズリサーチの手法  (KA03070E)

引用文献 (12件)：

• A. Marchetti-Spaccamela and C. Vercellis, ′′Stochastic on-line knapsack problems,′′ Mathematical Programming, 68, pp. 73-104, 1995.
• G. S. Lueker, ′′Average-case analysis of off-line and on-line knapsack problems,′′ Journal of Algorithms, 29, pp. 277-305, 1998.
• P. Dutting, M. Feldman, T. Kesselheim and B. Lucier, ′′Prophet inequalities made easy: Stochastic optimization by pricing non-stochastic inputs,′′ In Proceedings of the 58th Annual IEEE Symposium on Foundations of Computer Science (FOCS'17), pp. 540-551, 2017.
• M. Babaioff, N. Immorlica, D. Kempe and R. Kleinberg, ′′A knapsack secretary problem with applications,′′ In Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM'07), pp. 16- 28, 2007.
• M. Babaioff, J. D. Hartline and R. D. Kleinberg, ′′Selling banner ads: Online algorithms with buyback,′′ In Proceedings of the 4th Workshop on Ad Auctions, 2008.

タイトルに関連する用語 (3件)： オンライン ,  ナップサック問題 ,  アルゴリズム