Posi-modular systems with modulotone requirements under permutation constraints
Posi-modular systems with modulotone requirements under permutation constraints
复制标题
排列约束下具有模调要求的正模系统
DOI：
10.1142/s1793830910000474
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
Kazuhisa Makino
中科院分区：
文献类型：
--
作者：
Toshimasa Ishii;Kazuhisa Makino
给定有限集V上的一个系统（V，f，r），该系统由一个正模函数f：2V → R和一个模调函数r：2V → R组成，我们考虑寻找一个极小集R <$V使得f（X）≥ r（X）对所有X <$V-R.这个问题称为横截问题，在[M. Sakashita，K. Makino，H. Nagamochi和S. Fujishige，Minimum transversals in posi-modular systems，SIAM J.Discrete Math.23（2009）858 - 871]作为无向图和超图中具有边连通性要求的源定位问题和外部网络问题的自然推广。Tamura，H. Sugawara，M. Sengoku和S. Shinoda，Plural cover problem on undirected flow networks，IEICE Trans.J81-A（1998）863 - 869]对于源定位问题，我们证明了如果r是π-单调的，则横向问题可以通过简单的贪婪算法来解决，其中模调函数r是π-单调的，如果存在V的置换π使得函数pr：与r相关联的V × 2V → v满足pr（u，W）≥ pr（v，W），对所有W <$V和u，v ∈ V，π（u）≥ π（v）。在这里，我们证明了任何模调函数r都可以由pras r（X）= max {pr（v，W）|v ∈ X <$V-W}.我们还证明了π-单调函数r的横截问题在极小亏集上的结构性质，即，存在一个基本树T，使得对T中的所有弧（u，v）π（u）≤ π（v），作为推论，给出了源定位问题贪婪算法正确性的另一种证明，并证明了分数阶横截问题也可以用类似于横截问题的算法求解.
Given a system (V, f, r) on a finite set V consisting of a posi-modular function f : 2V→ ℝ and a modulotone function r : 2V→ ℝ, 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 in [M. Sakashita, K. Makino, H. Nagamochi and S. Fujishige, Minimum transversals in posi-modular systems,SIAM J. Discrete Math.23(2009) 858–871] as a natural generalization of the source location problem and external network problem with edge-connectivity requirements in undirected graphs and hypergraphs.By generalizing [H. Tamura, H. Sugawara, M. Sengoku and S. Shinoda, Plural cover problem on undirected flow networks,IEICE Trans.J81-A(1998) 863–869] 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→ ℝ 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 pras r(X) = max{pr(v, W) | v ∈ X ⊆ V - W}.We also show the structural properties on the minimal deficient setsfor the transversal problem for π-monotone function r, i.e., there exists a basic tree T forsuch 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.