文献

J-GLOBAL ID：202202221839185833   整理番号：22A0967064

ポシモジュラ関数最適化【JST・京大機械翻訳】

Posimodular Function Optimization

著者 (4件)： Halldorsson Magnus M. (ICE-TCS, School of Computer Science, Reykjavik University, Reykjavik, Iceland) ,  Ishii Toshimasa (Graduate School of Economics, Hokkaido University, Sapporo, Japan) ,  Makino Kazuhisa (Research Institute for Mathematical Sciences, Kyoto University, Kyoto, Japan) ,  Takazawa Kenjiro (Faculty of Science and Engineering, Hosei University, Tokyo, Japan)
資料名： Algorithmica  (Algorithmica)
巻： 84  号： 4  ページ： 1107-1131  発行年： 2022年 
JST資料番号： T0530A  ISSN： 0178-4617  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： ドイツ (DEU)  言語： 英語 (EN)

抄録/ポイント： 有限集合V上の関数[数式:原文を参照]は,[数式:原文を参照]が全ての[数式:原文を参照]に対してポジモジュラである。ポジモジュラ関数は,非指向性カット関数のような組合せ最適化においてしばしば発生する。ポジモジュラ関数fがオラクルアクセスによって与えられるとき,f(X)を最小にする非空部分集合Xを見つける問題を考察した。ポジモジュラ関数最小化は,カット関数の別の一般化を形成するサブモジュラ関数最小化の多項式可解性に対比して,指数関数的時間を必要とすることを示した。一方,問題は,fの画像(または範囲)のサイズDに関して,固定パラメータである。より詳細には,[数式:原文を参照]時間は必要であり,[数式:原文を参照]は十分であり,[数式:原文を参照]は1つの機能評価と[数式:原文を参照]の時間を示す。fの画像が整数dの[数式:原文を参照]であるとき,[数式:原文を参照]時間は十分であった。また,時間[数式:原文を参照]においてfを最小化するすべての集合を生成することができた。最後に,与えられたポジモジュラ関数を最大化する問題も考慮し,それは,それが,一般に,少なくとも[数式:原文を参照]時間を必要とし,一方,[数式:原文を参照]がfの画像であるとき,整数[数式:原文を参照]に対して,時間計算量[数式:原文を参照]を有することを示した。Copyright The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature 2022 Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： *関数 ,  *最適化 ,  多項式 ,  指数関数 ,  指向性
準シソーラス用語： 決定可能性 ,  *関数最適化 ,  オラクル ,  組合せ最適化 , 【Automatic Indexing@JST】

著者キーワード (3件)： Posimodular機能 ,  アルゴリズム ,  下界

分類 (2件)： 計算理論  (JB02000A) ,  その他のオペレーションズリサーチの手法  (KA03070E)

タイトルに関連する用語 (1件)： 関数最適化