劣モジュラ制約下の凸最適化問題について
スポンサーリンク
概要
- 論文の詳細を見る
本稿では劣モジュラ制約下の凸最適化問題を扱う.変数分離型凸関数の最小化問題に対する分解アルゴリズムにより最適化の有理数性のシンプルな十分条件が得られることを示し,辞書式最適基問題(藤重,1980)と劣モジュラ効用配分問題(Jain-Vazirani,2007)の等価性などの性質を導く.また,パラメトリック劣モジュラ関数最小化を用いた,分解アルゴリズムの理論的に高速な実行手法を与える.さらに,あるクラスの非変数分離型凸関数最小化が多項式時間で解けることを指摘する.
- 2007-04-19
著者
関連論文
- 劣モジュラ費用集合被覆問題 (21世紀の数理計画 : アルゴリズムとモデリング)
- 劣モジュラ構造を有する連続最適化問題の組合せ的アルゴリズム(研究会推薦博士論文速報)
- 劣モジュラ制約下の凸最適化問題について
- 高速なパラメトリック劣モジュラ関数最小化とその応用
- 劣モジュラ罰則を含む組合せ最適化問題の緩和問題に対するLovasz拡張とノンスムーズ凸最適化手法を用いた効率的解法
- 劣モジュラ罰則を含む組合せ最適化問題の緩和問題に対する Lovasz 拡張とノンスムーズ凸最適化手法を用いた効率的解法
- 基礎技術としての劣モジュラ最適化(最先端を目指す若手研究者達)
- 劣モジュラ費用集合被覆問題
- イベント報告:東京工業大学サイエンスカフェ「計算で何ができるか?」 (特集 数学版サイエンスカフェ)
- パラメトリックな劣モジュラ交わり問題の構造理論 (21世紀の数理計画 : 最適化モデルとアルゴリズム)
- DS-1-5 パラメトリックな劣モジュラ交わり問題の構造理論(DS-1. COMP-NHC学生シンポジウム,シンポジウムセッション)
- 劣モジュラ多面体上の最適化アルゴリズムの研究
- 劣モジュラ多面体内直線探索問題に対する強多項式時間アルゴリズム(組合せ最適化(6))
- 劣モジュラ多面体内直線探索問題に対する強多項式時間アルゴリズム
- A Strongly Polynomial Algorithm for Line Search in Submodular Polyhedra
- B-17-29 ヘテロジニアス型コグニティブ無線ネットワークにおけるRAN選択問題の厳密最適化(B-17.ソフトウェア無線,一般セッション)
- 劣モジュラ性に基づく知能情報処理への新展開(離散構造処理系-知能情報処理を支えるアルゴリズムの技法)
- 劣モジュラ性に基づく知能情報処理への新展開
- 劣モジュラ制約下におけるオンライン予測(機械学習一般とその応用)