劣モジュラ関数最小化の強多項式時間アルゴリズム
スポンサーリンク
概要
- 論文の詳細を見る
劣モジュラ関数の最小化は,離散最適化における基本的な問題である.Grotschel-Lovasz-Schrijver (1981)は,楕円体法を用いて,この問題が多項式時間で解けることを示した.しかし,楕円体法が実際には極めて非効率的であるため,組合せ的な多項式時間アルゴリズムの開発が長い間望まれてきた. 本論文では,劣モジュラ関数を最小化する最初の組合せ的な多項式時間アルゴリズムを提示する.このアルゴリズムは,各枝の容量が一様な完全有向グラフを用いた新たなスケーリング技法を利用しており,計算量が台集合の大きさと関数値の最大ビット長の多項式で押えられる.さらに,計算量が台集合の大きさの多項式で押えられる強多項式時間アルゴリズムも提示する.
- 一般社団法人情報処理学会の論文
- 1999-11-08
著者
-
岩田 覚
東京大学大学院工学系研究科計数工学専攻
-
FLEISCHER Lisa
Department of Computer Science, Dartmouth College
-
Fleischer Lisa
Department Of Computer Science Dartmouth College
-
Fleischer Lisa
Department Of Industrial Engineering And Operations Research Columbia University
-
藤重 悟
大阪大学基礎工学研究科システム科学分野
-
岩田 覚
Division of Systems Science, Graduate School of Engineering Science, Osaka University
-
藤重 悟
Division of Systems Science, Gradeate School of Engineering Science, Osaka University
関連論文
- 1-B-6 線形計画問題の符号可解性(組合せ最適化(1))
- 符号対称行列のSylvester指数(組合せ最適化(6))
- M凸劣モジュラ流問題に対する容量スケーリング法
- Algorithms and Lower Bounds for Submodular Cuts and Approximating Submodular Functions (Combinatorial Optimization and Discrete Algorithms)
- Approximate- Weight-Splitting Algorithm for a Minimum Common Base of a Pair of Matroids(Mathematical Structure of Optimization Theory)
- マトロイドの最適共通基問題に対するオークション算法(グラフ・ネットワーク)
- 第10回「整数計画法・組合せ最適化」国際会議(IPCO X)に参加して
- 劣モジュラ関数の最小化
- 双劣モジュラ関数最小化
- 無向ネットワークにおける流量要求を満たす施設配置問題
- 劣モジュラ関数最小化の強多項式時間アルゴリズム (新しいパラダイムとしてのアルゴリズム工学)
- 劣モジュラ関数最小化の強多項式時間アルゴリズム
- ネットワーク上の被覆型施設配置問題(グラフ・ネットワーク(3))
- 設備更改のスケジューリング問題への基本分割の応用(スケジューリング)
- 1-B-9 グラフの向き付けに関する最適化問題の解法(組合せ最適化(2))
- 多項式行列に対する組合せ論的緩和法の実現について(組合せ最適化)
- 分割行列の階層的分解(II) : 同値変換(離散数学)
- 分割行列の階層的分解(I) : 相似変換(離散数学)
- Gale-Shapleyの安定マッチングアルゴリズムのM〓凹関数対への拡張(最適化(1))
- 一般化最小費用独立フロー問題とその多項式時間アルゴリズム(グラフ・ネットワーク(1))
- 木構造の動的ネットワークにおける施設配置問題(グラフ・ネットワーク(2))
- L.R. Ford, Jr., & D.R. Fulkerson : Flows in Networks(20世紀の名著名論)
- 木構造ネットワークの敷設費用配分ゲーム(ゲーム理論(2))
- 劣モジュラシステムの基本構造とHitchcock型独立流(グラフ・ネットワーク(2))
- "一般性"を仮定した分割行列に関する最大最小定理とDulmage-Mendelsohn型分解(組合せ最適化)
- 独立マッチングの基本構造に関する一定理(組合せ最適化)