文献

J-GLOBAL ID：202002260918464996   整理番号：20A0593580

ナップサック制約下の単調サブモジュラ関数を最大化するためのストリーミングアルゴリズム【JST・京大機械翻訳】

Streaming Algorithms for Maximizing Monotone Submodular Functions Under a Knapsack Constraint

著者 (3件)： Huang Chien-Chung (DIENS, Ecole Normale Superieure, Universite PSL, Paris, France) ,  Kakimura Naonori (Department of Mathematics, Keio University, Yokohama, Japan) ,  Yoshida Yuichi (National Institute of Informatics, Tokyo, Japan)
資料名： Algorithmica  (Algorithmica)
巻： 82  号： 4  ページ： 1006-1032  発行年： 2020年 
JST資料番号： T0530A  ISSN： 0178-4617  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： ドイツ (DEU)  言語： 英語 (EN)

抄録/ポイント： 本論文では,ストリーミング設定におけるナップサック制約を受ける単調サブモジュール関数を最大化する問題を考察した。特に,要素は連続的に到着し,任意の時点で,アルゴリズムは一次メモリに保存されたデータの小部分にのみアクセスする。この問題に対して,データを通して単一パスのみを必要とする[数式:原文を参照]近似アルゴリズムを提案した。さらに,データを通して一定数のパスを必要とする[数式:原文を参照]近似アルゴリズムを提案した。両アルゴリズムの必要メモリ空間はナップサック容量と[数式:原文を参照]のサイズにのみ依存する。Copyright Springer Science+Business Media, LLC, part of Springer Nature 2019 Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： *アルゴリズム ,  近似法 ,  *ストリーミング ,  記憶装置
準シソーラス用語： 近似アルゴリズム ,  *ストリーミングアルゴリズム , 【Automatic Indexing@JST】

著者キーワード (4件)： 劣モジュラ関数 ,  シングルパスストリーミング ,  マルチパスストリーミング ,  定数近似

分類 (2件)： その他のオペレーションズリサーチの手法  (KA03070E) ,  分子・遺伝情報処理  (JE15040B)

タイトルに関連する用語 (7件)： ナップ ,  サック ,  制約 ,  サブ ,  関数 ,  最大化 ,  ストリーミングアルゴリズム