文献

J-GLOBAL ID：201702260548974393   整理番号：17A1913672

劣モジュラ最大化に対する高速な最良優先探索

Fast Best-first Search for Submodular Function Maximization

著者 (2件)： 坂上晋作 (NTT コミュニケーション科学基礎研) ,  石畠正和 (北大 大学院情報科学研究科)
資料名： 電子情報通信学会技術研究報告  (IEICE Technical Report (Institute of Electronics, Information and Communication Engineers))
巻： 117  号： 293(IBISML2017 35-89)  ページ： 277-282  発行年： 2017年11月02日 
JST資料番号： S0532B  ISSN： 0913-5685  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： ナップサック制約付きの単調劣モジュラ最大化問題に対し,高速な最良優先探索法を提案する。提案法は指数的な計算量を必要とし得る一方で,任意のα(0≦α≦1)に対しα-近似解を出力することができる。提案法では探索時に用いるヒューリスティック関数値の計算を劣モジュラ最大化問題に帰着し,その上界値を高精度に計算する方法を用いて高速化を実現する。(著者抄録)

シソーラス用語： *関数 ,  ナップサック問題 ,  制約条件 ,  性質 ,  *最大化問題 ,  解 ,  発見的方法 ,  優先度 ,  限界 ,  高速化 ,  *捜索
準シソーラス用語： ヒューリスティック ,  *解探索 ,  近似解 ,  上界 ,  単調性 ,  *劣モジュラ関数

分類 (2件)： 人工知能  (JE08000Z) ,  その他のオペレーションズリサーチの手法  (KA03070E)

引用文献 (23件)：

• N. Alon, I. Gamzu, and M. Tennenholtz. Optimizing budget allocation among channels and influencers. In Proceedings of the 21st International Conference on World Wide Web, WWW '12, pages 381-388, New York, NY, USA, 2012. ACM.
• D. Avis and K. Fukuda. Reverse search for enumeration. Discrete Appl. Math., 65(1):21-46, 1996. First International Colloquium on Graphs and Optimization.
• F. Bach. Learning with submodular functions: A convex optimization perspective. Foundations and Trends? in Machine Learning, 6(2-3):145-373, 2013.
• W. Chen, Y. Chen, and K. Weinberger. Filtered search for submodular maximization with controllable approximation bounds. In Proceedings of the 18th International Conference on Artificial Intelligence and Statistics, volume 38, pages 156-164. PMLR, 09-12 May 2015.
• M. Conforti and G. Cornu?jols. Submodular set functions, matroids and the greedy algorithm: Tight worst-case bounds and some generalizations of the Rado-Edmonds theorem. Discrete Appl. Math., 7(3):251-274, 1984.

タイトルに関連する用語 (3件)： 最大化 ,  優先 ,  探索