順列制約をみたす模調要求をもつ正モジュラシステムについて
スポンサーリンク
概要
- 論文の詳細を見る
有限集合 V ,正モジュラ関数 f : 2V → R および模調関数 r : 2V → R からなるシステム (V, f, r) において,すべての X ⊆ V - R に対し f (X) ≧ r (X) が成り立つような要素数最小の集合 R ⊆ V を求める問題を考える.この問題は横断問題と呼ばれ,Sakashita ら 6) により無向グラフまたは無向ハイパーグラフにおける辺連結度要求をもつ供給点配置問題および外部ネットワーク問題を一般化した枠組みとして導入された.本論文では,任意の模調関数 r が r (X) = max{pr (v,W) | v ∈ X ⊆ V - W} をみたす関数 pr : V × 2V → R により特徴づけられることを示し,さらに供給点配置問題に対する Tamura らの結果 8) を一般化し,r が π-単調であるとき横断問題が簡潔な貪欲法により解けることを示す.ここで,すべての W ⊆ V と π(u) ≧ π(v) であるすべての 2 要素 u, v ∈ V に対し pr (u,W) ≧ pr (v,W) が成り立つ V の順列 π が存在するとき,r は π-単調であるという.また,r が π-単調であるときの横断問題における極小不足集合族 W に関する構造的性質も示す.すなわち,すべての点 u とその親 v に対し π(u) ≦ π(v) が成り立つような W に対する基本木が存在することを示す.この性質は,供給点配置問題に対する貪欲法の正当性の別の証明を与える.さらに,フラクショナル横断問題が,横断問題に対するアルゴリズムと同様の手法により解けることを示す.
- 2009-11-20
著者
関連論文
- 点集合間の辺連結度を増大させる問題
- 平成20年秋季研究発表会ルポ(情報の窓)
- 2-F-11 An O(n log^2 n)-Time Algorithm for L(2,1)-Labeling of Trees
- RA-002 木のL(2,1)-ラベリングのためのO(n log^2 n)時間アルゴリズム(モデル・アルゴリズム・プログラミング,査読付き論文)
- 木のL(2,1)-ラベリングに対するO(n^)時間アルゴリズム
- 木の(p, q)-全ラベリング問題
- 安心・安全社会構築のためのシステム人間科学の創成(テーマ関連/オーガナイズドセッション1)
- 外平面的グラフの(2,1)-全ラべリング数のタイトな上界
- 順列制約をみたす模調要求をもつ正モジュラシステムについて
- 木のL(2, 1)-ラベリングに対する線形時間アルゴリズム
- 無向グラフにおける単調な要求関数を持つ辺連結度増大問題
- ホーン理論の内包・外包に対する演繹推論
- 有限グラフ上のランダムウォークの脱乱択化
- 1-D-4 木構造動的ネットワークにおけるα-最速到達フロー(離散アルゴリズム(1))
- 2-I-4 整数線形システムの実行可能性問題に対する計算複雑さの指標(離散最適化(3))
- 2-I-3 ネットワークデザインゲームにおけるポテンシャル最小化(離散最適化(3))
- 単調な論理関数の双対化について
- 1-C-8 キャンセルコスト付きオンラインナップサック問題(離散最適化(1))
- 1-C-10 疎な線形相補性問題に対する組合せ的アルゴリズム(離散最適化(1))
- 2-A-11 ロバスト独立システム(離散最適化(3))