Generalized polymatroid
The term g-polymatroid is shorthand for "generalized polymatroid." The family of g-polymatroids includes the independent and spanning set polytopes of matroids.
Definitions of Generalized Polymatroids
1. The original definition [1] of a g-polymatroid is any polyhedron of the form
- {x∈\Rn∣∀S⊂[n]:p(S)≤x(S)≤b(S)}
where the set functions p, b are respectively super- and submodular, and they satisfy the cross-inequality b(X)−p(Y)≥b(X∖Y)−p(Y∖X) for all X,Y⊂[n].
1'. To write the previous definition more compactly, for i∈[n] define a set-function fi on [n]∖{i} by fi(S):=f(S∪{i})−f(S). Then equivalent conditions on b and p are that for all i, bi is monotonically nonincreasing, pi is monotonically nondecreasing, and bi(S)≥pi(T) for all disjoint S, T.
2. A second equivalent definition [1][2][3] is that a g-polymatroid is a polyhedron obtained by taking a base polyhedron and applying a projection which deletes some coordinates.
3. For full-dimensional polyhedra, the following is also equivalent [4]: a full-dimensional polyhedron of the form
- {x∈\Rn∣Ax≤b,Ax′≥b′} where A and A′ are 0-1 matrices
is a g-polymatroid if and only if for every bounded primal objective, there is an optimal dual whose support corresponds to a laminar family. (Here, each dual variable corresponds to a row of A or A' and we identify these 0-1 n-vectors with subsets of [n] in the natural way.)
4. Integer g-polymatroids are exactly the polyhedra that satisfy the strong linking property [5].
As is typical with sub/supermodular polyhedra, one can still obtain a g-polymatroid even if the functions b and p have some subfamily of 2[n] as their ground set, provided that certain "crossing" conditions hold; and if all the data defining the polyhedron are integral, then the polyhedron is integral. See the general references [2][6][7] for this and other facts.
See also
- Open problem about characterizing integral g-polymatroids
References
- ↑ 1.0 1.1 A. Frank. Generalized polymatroids. In A. Hajnal, L. Lovász, and V. T. Sós, editors, Finite and Infinite Sets, Vol. I (Eger 1981), volume 37 of Colloq. Math. Soc. János Bolyai, pages 285–294. North-Holland, 1984. author link
- ↑ 2.0 2.1 Frank, A. and Tardos, É. Generalized polymatroids and submodular flows, Mathematical Programming 42(1):489–563, 1988. DOI link, author link
- ↑ S. Fujishige, A note on Frank's generalized polymatroids, Discrete Applied Mathematics 7 105n‐109, 1984. DOI link
- ↑ A. Frank, T. Király, J. Pap, D. Pritchard, Characterizing and recognizing generalized polymatroids, DOI link, EGRES Technical Report.
- ↑ T. Király, Base polyhedra and the linking property, EGRES Technical Report no. 2016-06
- ↑ Schrijver, A. Combinatorial Optimization, section 49.11b. Springer, 2003.
- ↑ Frank, A. and Király, T. A Survey on Covering Supermodular Functions, Research Trends in Combinatorial Optimization (Bonn 2008), Cook, W, Lovász, L. and Vygen, J., editors, Springer. Chapter 6, pages 87–126, 2009. DOI link pdf link
