高速なパラメトリック劣モジュラ関数最小化とその応用

• Item type: SIG Technical Reports(1)
• 公開日: 2007-09-21
• タイトル: 高速なパラメトリック劣モジュラ関数最小化とその応用
• タイトル / 言語: en
• タイトル: A Faster Parametric Submodular Function Minimization Algorithm and Applications
• 言語: eng
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 東京大学
• 著者所属(英): en
• 著者所属(英): University of Tokyo
• 著者名: 永野, 清仁
• 著者名(英): Kiyohito, Nagano
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 本研究では強射列に対するパラメトリック劣モジュラ関数最小化を扱うず最近Orlin により得られた劣モジュラ関数最小化アルゴリズムがこの枠組みに拡張可能であることを示して効率的アルゴリズムを与える．本手法は最小比問題や劣モジュラ制約凸最適化問題の高速解法への応用がある．また，今回新たに劣モジュラシステムのロバスト性評価がパラメトリック劣モジュラ関数最小化を用いて効率的に実行可能であることを示した．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: This paper discusses the parametric submodular function minimization problem for strong map sequences. We show that the recent submodular function minimization algorithm of Orlin can be extended to this framework. Applications include faster algorithms for minimum ratio problems and convex optimization over submodular constraints. We also show that the robustness function of a submodular system can be computed efficiently via parametric submodular function minimization.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 情報処理学会研究報告アルゴリズム（AL）; 巻 2007, 号 92(2007-AL-114), p. 41-48, 発行日 2007-09-21
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会