2024-03-28T23:38:24Zhttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_oaipmhoai:ipsj.ixsq.nii.ac.jp:000668522023-04-27T10:00:04Z01164:02592:05623:05923
Posi-modular Systems with Modulotone Requirements under Permutation Constraints順列制約をみたす模調要求をもつ正モジュラシステムについてenghttp://id.nii.ac.jp/1001/00066852/Technical Reporthttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_action_common_download&item_id=66852&item_no=1&attribute_id=1&file_no=1Copyright (c) 2009 by the Information Processing Society of Japan小樽商科大学東京大学石井, 利昌牧野, 和久有限集合 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 に対する基本木が存在することを示す.この性質は,供給点配置問題に対する貪欲法の正当性の別の証明を与える.さらに,フラクショナル横断問題が,横断問題に対するアルゴリズムと同様の手法により解けることを示す.Given a system (V, f, r) on a finite set V consisting of a posi-modular function f : 2V → R and a modulotone function r : 2V → R, we consider the problem of finding a minimum set R ⊆ V such that f(X) ≧ r(X) for all X ⊆ V - R. The problem, called the transversal problem, was introduced by Sakashita et al. 6) as a natural generalization of the source location problem and external network problem with edge-connectivity requirements in undirected graphs and hypergraphs. By generalizing 8) for the source location problem, we show that the transversal problem can be solved by a simple greedy algorithm if r is π-monotone, where a modulotone function r is π-monotone if there exists a permutation π of V such that the function pr : V × 2V → R associated with r satisfies pr(u,W) ≧ pr(v,W) for all W ⊆ V and u, v ∈ V with π(u) ≧ π(v). Here we show that any modulotone function r can be characterized by pr as r(X) = max{pr(v,W) | v ∈ X ⊆ V - W}. We also show the structural properties on the minimal deficient sets W for the transversal problem for π-monotone function r, i.e., there exists a basic tree T for W such that π(u) ≦ π(v) for all arcs (u, v) in T, which, as a corollary, gives an alternative proof for the correctness of the greedy algorithm for the source location problem. Furthermore, we show that a fractional version of the transversal problem can be solved by the algorithm similar to the one for the transversal problem.AN1009593X研究報告アルゴリズム(AL)2009-AL-1275182009-11-202009-12-08