Polyhedral structure of submodular and posi-modular systems
Polyhedral structure of submodular and posi-modular systems
复制标题
子模和正模系统的多面体结构
DOI：
10.1016/s0166-218x(00)00246-8
复制
发表时间：
1998
影响因子：
1.1
通讯作者：
T. Ibaraki
中科院分区：
文献类型：
--
作者：
H. Nagamochi;T. Ibaraki
设V是一个有限集，R是实数集。集合函数f：2 V → R称为交子模，如果f（X）+f（Y），X-Y和Y-X成立。我们考虑多面体P={z∈ R-V| z（X）<$f（X），<$X ∈ 2 V}对于系统（V，f）具有相交的子模和正模集函数f：2 V → R，其中R-V表示|V|- 维非正向量和z（X），对于z∈ R− V和X <$V由∑i∈Xz（i）定义。我们首先证明存在层流（即，不相交）族X <$2V −{Z，V}，使得P的特征为{z∈ R−V| z（X）<$f（X），<$X∈ X } .在此基础上，我们可以在多项式时间内解决增加网络的边连通度的问题，以使具有增加权重的边的顶点的数量最小化。
Let V be a finite set, and R be the set of reals. A set function f : 2V→ R is called intersecting submodular if f(X)+f(Y)⩾f(X∩Y)+f(Y∪X) for all intersecting X,Y⊂V, and intersecting posi-modular if f(X)+f(Y)⩾f(X−Y)+f(Y−X) for all intersecting X,Y⊂V, where X and Y intersecting if X∩Y≠∅, X−Y≠∅ and Y−X≠∅ hold. We consider the polyhedron P={z∈ R−V| z(X)⩽f(X), ∀X ∈2V} for a system (V,f) with an intersecting submodular and posi-modular set function f : 2V→ R , where R−Vdenotes the set of |V|-dimensional nonpositive vectors and z(X) for a z∈ R−Vand X⊆V is defined by ∑i∈Xz(i). We first prove that there is a laminar (i.e., nonintersecting) family X ⊆2V−{∅,V} such that P is characterized by {z∈ R−V| z(X)⩽f(X), ∀X∈ X } . Based on this, we can solve in polynomial time the problem of augmenting edge-connectivity of a network so as to minimize the number of vertices having edges whose weights are increased.