劣モジュラ費用集合被覆問題
スポンサーリンク
概要
- 論文の詳細を見る
本研究では,頂点被覆問題,枝被覆問題,集合被覆問題,それぞれの目的関数を線形な関数から非負な劣モジュラ関数で置き換えて一般化した問題を扱う.これらの問題に対し,劣モジュラ関数の離散凸性を用いた近似アルゴリズムを設計する.まず,劣モジュラ頂点被覆問題に対しては,連続緩和問題の半整数性を証明し,それ利用したラウンディングによる 2 近似アルゴリズムを与えた.さらに半整数的な最適解が劣モジュラ関数最小化によって求まることを示した.劣モジュラ費用集合被覆問題に対しては,最大重複度が定数でおさえられる場合,ラウンディングアルゴリズムと主双対アルゴリズムの両方で定数近似率が達成されることを示した.劣モジュラ枝被覆問題に対しては,近似可能性の本質的にタイトな下界を与えた.
- 一般社団法人情報処理学会の論文
- 2009-09-08
著者
関連論文
- 非線形時変回路に対する混合方程式の組合せ論的解析 : グラフ構造による順良指数の特徴付け (21世紀の数理計画 : アルゴリズムとモデリング)
- 劣モジュラ費用集合被覆問題 (21世紀の数理計画 : アルゴリズムとモデリング)
- 「距離の暴虐」を超えて
- 劣モジュラ構造を有する連続最適化問題の組合せ的アルゴリズム(研究会推薦博士論文速報)
- 劣モジュラ制約下の凸最適化問題について
- 2-D-3 混合行列束のKronecker標準形の組合せ論的解析(離散・組合せ最適化(5))
- 電気回路の混合解析における微分代数方程式の指数最小化 (21世紀の数理計画 : 最適化モデルとアルゴリズム)
- 高速なパラメトリック劣モジュラ関数最小化とその応用
- 劣モジュラ罰則を含む組合せ最適化問題の緩和問題に対するLovasz拡張とノンスムーズ凸最適化手法を用いた効率的解法
- 劣モジュラ罰則を含む組合せ最適化問題の緩和問題に対する Lovasz 拡張とノンスムーズ凸最適化手法を用いた効率的解法
- 離散凸最適化ソルバとデモンストレーションソフトウェアの公開
- 2-E-3 混合多項式行列の小行列式の最大次数を計算する組合せ緩和法(離散最適化(1))
- 基礎技術としての劣モジュラ最適化(最先端を目指す若手研究者達)
- 「距離の暴虐」を超えて
- Index Reduction for Differential-Algebraic Equations by Discrete Optimization Techniques(Mathematical Sciences for Large Scale Numerical Simulations)
- 線形マトロイド・グラフアレンジメント・半順序での数え上げ問題に対する組合せ的・幾何的アプローチ
- 均質システムの自律可制御性解析
- 凸費用劣モジュラ流に対する容量スケーリング法
- 1-B-6 線形計画問題の符号可解性(組合せ最適化(1))
- 符号対称行列のSylvester指数(組合せ最適化(6))
- M凸劣モジュラ流問題に対する容量スケーリング法
- 劣モジュラ費用集合被覆問題
- 混合行列束の Kronecker 標準形の組合せ論的解析
- 混合行列束のKronecker標準形の組合せ論的解析
- AT-3-2 劣モジュラ最適化と近似アルゴリズム(AT-3.コンカレントシステム理論の新しい流れ,チュートリアルセッション,ソサイエティ企画)
- 劣モジュラ流問題に対するコストスケーリング算法(組み合わせ最適化(1))
- Approximate- Weight-Splitting Algorithm for a Minimum Common Base of a Pair of Matroids(Mathematical Structure of Optimization Theory)
- マトロイドの最適共通基問題に対するオークション算法(グラフ・ネットワーク)
- 1-A-9 劣モジュラ最適化(計算と最適化(1))
- 2-C-4 独立偶因子の組合せ的アルゴリズム(離散最適化(3))
- KSMAP「OR若手の会」の紹介
- 一般グラフのDulmage-Mendelsohn型分解(グラフ・ネットワーク(2))
- 選択組立におけるマッチング算法(組合せ最適化(2))
- 1-B-9 グラフの向き付けに関する最適化問題の解法(組合せ最適化(2))
- Primal-Dual Combinatorial Relaxation Algorithms for the Maximum Degree of Subdeterminants
- 多項式行列に対する組合せ論的緩和法の実現について(組合せ最適化)
- イベント報告:東京工業大学サイエンスカフェ「計算で何ができるか?」 (特集 数学版サイエンスカフェ)
- 分割行列の階層的分解(II) : 同値変換(離散数学)
- 分割行列の階層的分解(I) : 相似変換(離散数学)
- パラメトリックな劣モジュラ交わり問題の構造理論 (21世紀の数理計画 : 最適化モデルとアルゴリズム)
- DS-1-5 パラメトリックな劣モジュラ交わり問題の構造理論(DS-1. COMP-NHC学生シンポジウム,シンポジウムセッション)
- 劣モジュラ多面体上の最適化アルゴリズムの研究
- 劣モジュラ多面体内直線探索問題に対する強多項式時間アルゴリズム(組合せ最適化(6))
- 劣モジュラ多面体内直線探索問題に対する強多項式時間アルゴリズム
- A Strongly Polynomial Algorithm for Line Search in Submodular Polyhedra
- L.R. Ford, Jr., & D.R. Fulkerson : Flows in Networks(20世紀の名著名論)
- 木構造ネットワークの敷設費用配分ゲーム(ゲーム理論(2))
- 劣モジュラシステムの基本構造とHitchcock型独立流(グラフ・ネットワーク(2))
- "一般性"を仮定した分割行列に関する最大最小定理とDulmage-Mendelsohn型分解(組合せ最適化)
- 独立マッチングの基本構造に関する一定理(組合せ最適化)
- B-17-29 ヘテロジニアス型コグニティブ無線ネットワークにおけるRAN選択問題の厳密最適化(B-17.ソフトウェア無線,一般セッション)
- 劣モジュラ性に基づく知能情報処理への新展開(離散構造処理系-知能情報処理を支えるアルゴリズムの技法)
- 劣モジュラ性に基づく知能情報処理への新展開
- 劣モジュラ制約下におけるオンライン予測(機械学習一般とその応用)