抄録/ポイント：
抄録/ポイント
文献の概要を数百字程度の日本語でまとめたものです。
部分表示の続きは、JDreamⅢ(有料)でご覧頂けます。
J-GLOBALでは書誌(タイトル、著者名等)登載から半年以上経過後に表示されますが、医療系文献の場合はMyJ-GLOBALでのログインが必要です。
ナップサック制約を受ける非負モノトーンサブモジュラ関数を最大化する問題を考察し,それはまた,Budgeted Submodular Maximization(BSM)問題として知られている。Sviridenko(2004)は最適解の3つの適切な要素を推測し,次に greedy欲なアルゴリズムを実行することにより,BSMに対してα=1-1/e≒0.632の最適近似比を得ることができることを示した。しかし,推定(計数)3要素の必要性は,O(n ̄5)の時間複雑性をもたらすので,Sviridenko非現実的のアルゴリズムを作るが,これは,Badanidiyuru&Vondrak(2014)の閾値化技術を用いてわずかに改善されるが,大まかにO(n ̄4)のみである。本論文における主な結果は,より少ない推測スフィスを示した。特に,2つの推測だけを作ることによって,著者らは,およそO(n ̄3)の改良した時間複雑性によって,αの同じ最適近似比率を得た。さらに,単一推測のみを行うことで,ほぼO(n ̄2)時間で0.6174>0.9767αの良好な近似比を得た。著者らの研究の前に,BSMに対するαに近い近似比を得ることが知られている唯一のアルゴリズムは,Sviridenkoのアルゴリズムおよび(α-ε)近似を達成するEne&Nguyen(2019)のアルゴリズムであった。しかし,Ene&Nguyenのアルゴリズムは,(1/ε) ̄O(1/ε ̄4)nlog ̄2n時間を必要とし,従って,(1/ε) ̄O(1/ε ̄4)は,εの中程度の値でさえ,非常に大きい。対照的に,解析したすべてのアルゴリズムは簡単で並列化可能であり,実用的な使用のための良好な候補になる。最近,Tangら(2020)は,既に長い研究歴史を持つ簡単な greedy欲アルゴリズムを研究し,その近似比が少なくとも0.405であることを証明した。この結果を改善し,このアルゴリズムの近似比が[0.427,0.462]の範囲内であることを示した。【JST・京大機械翻訳】
