劣モジュラ・システムに関連する基多面体のすべての面の特徴づけ
スポンサーリンク
概要
- 論文の詳細を見る
有限集合Eの部分集合の族からなる分配束Dと辺Dに定義される劣モジュラ関数fとの対(D、f)は劣モジュラ・システムと呼ばれる。ここで、φ∈D、f(φ)=0と仮定する。E∈Dであるとき、劣モジュラ・システム(D、f)の基多面体はB(f)={ x | x∈R^E、 ∀X∈D:x(X)≦f(X)、 x(E)=f(E) }と定義される。本論文では、基多面体B(f)の構造について考察を加え、B(f)のすべての面(faces)の特徴づけを与える。B(f)の各面は辺の周有な部分束に対応づけられ、このような部分束の全体DはB(f)の非空な面の全体Fに反同形である(ここで、D、Fを集合の句合関係に関する半順序集合と考える)。Dの構造に基づいて、面の間の接続関係、面の次元、面の端点および端射線を与える。この結果は、最近得られているところの(1)Bixby、 CuminghamとTopkisによるホリマトロイド多面体の端点に関連する半順序構造と連結成分、(2)冨澤による分配束によって定まる凸錐の端射線の特徴づけ、(3)Topkisによるホリマトロイド多面体の端点の隣接関係、の結果を特別な場合として含む。さらに、Dの部分束D_1が与えられ、fがD_1でモジュラであるとき、F(D_1)={ x | x∈B(f)、∀X∈D_1 : x(X)=f(X) }はB(f)の非空な面であり、面F(D_1)に対応する部分束D_2∈Dが一意に存在する。このようなD_1とD_2の間の関係を特徴づける定理を示す。ここでD_2はD_1の閉包と考えることができ、この閉包は、中村と伊理によって最近導入された最大骨格の概念と密接に関係している。以上の各種の特徴づけについて、算法論的な観点からも考察を加える。
著者
関連論文
- 劣モジュラ・システムに関連する基多面体のすべての面の特徴づけ
- 分配束上の劣モジュラ関数について
- The Minimum-Weight Ideal Problem for Signed Posets
- 線形計画問題に対する双対内点主シンプレックス法
- Signed Posets for Extreme Points of a Bisubmodular Polyhedron
- ∩,∪-closed Families and Signed Posets
- Proper Bisubmodular Systems and Bidirected Flows
- A Greedy Algorithm for Minimizing a Separable Convex Function over a Finite Jump system
- A Greedy Algorithm for Minimizing a Separable Convex Function over an Integral Bisubmodular Polyhedron
- 組合せ的制約をもつ線形システムの可制御性,可観測性
- SUMTから乗数法へ(新技術アラカルト)
- New Algorithms for the Intersection Problem of Submodular Systems
- 最小平均コストの閉路に基づく劣モジュラ・フロー問題に対する一つのプライマルな算法