Polyhedral structure of submodular and posi-modular systems ?
Let V be a finite set, and be the set of reals. A set function 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 for a system (V,f) with an intersecting submodular and posi-modular set function , where denotes the set of |V|-dimensional nonpositive vectors and z(X) for a and X?V is defined by ?i?Xz(i). We first prove that there is a laminar (i.e., nonintersecting) family such that P is characterized by . 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.
submodular function posi-modular function minimum cut edge-connectivity augmentation core polyhedra