文献

J-GLOBAL ID：201702228689189878   整理番号：17A1360007

劣加法的集合関数の負荷分散最適化

Subadditive Load Balancing

著者 (2件)： 永野清仁 (群馬大) ,  岸本章宏 (IBM Res., IRL)
資料名： 情報処理学会研究報告(Web)  (IPSJ Technical Report (Web))
巻： 2017  号： AL-164  ページ： Vol.2017-AL-164,No.4,1-8 (WEB ONLY)  発行年： 2017年09月12日 
JST資料番号： U0451A  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： 劣モジュラ集合関数の最大化や最小化など,集合関数最適化の技術は昨今の人工知能や機械学習の分野において重要な役割を果たしている。劣加法的集合関数は,劣モジュラ性をシンプルに一般化した集合関数である。本研究では,劣加法的集合関数に関するミニマックスタイプの負荷分散最適化問題を扱い,モジュラ関数近似を用いた近似アルゴリズムを与える。また,集合関数が非負かつ劣加法的な場合について,このアルゴリズムの近似率を評価する。さらに,負荷分散最適化アルゴリズムをマルチロボット・ルーティング問題に適用し,アルゴリズムのパフォーマンスを計算機実験により評価する。(著者抄録)

シソーラス用語： 関数 ,  多面体 ,  *負荷分散 ,  *最適化問題 ,  順路問題 ,  計算機シミュレーション ,  *アルゴリズム
準シソーラス用語： 集合関数 ,  超立方体 ,  劣モジュラ集合関数 ,  劣加法性 ,  経路問題 ,  計算機実験 ,  最適化アルゴリズム

分類 (1件)： オペレーションズリサーチの基礎的数学理論  (KA03020B)

引用文献 (34件)：

• Bach, F.: Structured sparsity-inducing norms through submodular functions, NIPS, pp. 118-126 (2010).
• Bach, F.: Learning with Submodular Functions: A Convex Optimization Perspective, Foundations and Trends in Machine Learning, Vol. 6, No. 2-3, pp. 145-373 (2013).
• Bian, A. A., Buhmann, J. M., Krause, A. and Tschiatschek, S.: Guarantees for Greedy Maximization of Non-submodular Functions with Applications, CoRR, Vol. abs/1703.02100 (online), available from http://arxiv.org/abs/1703.02100 (2017).
• Edmonds, J.: Submodular functions, matroids, and certain polyhedra, Combinatorial Structures and Their Applications (Guy, R., Hanani, H., Sauer, N. and Sch?nheim, J., eds.), Gordon and Breach, pp. 69-87 (1970).
• Feige, U.: On Maximizing Welfare When Utility Functions Are Subadditive, SIAM J. Comput., Vol. 39, No. 1, pp. 122-142 (2009).

タイトルに関連する用語 (3件)： 加法 ,  集合関数 ,  分散最適化