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
- [math]\{x \in \R^n \mid \forall S \subset [n] : p(S) \le x(S) \le b(S)\}[/math]
where the set functions p, b are respectively super- and submodular, and they satisfy the cross-inequality [math]b(X) - p(Y) \ge b(X \backslash Y) - p(Y \backslash X)[/math] for all [math]X, Y \subset [n].[/math]
1'. To write the previous definition more compactly, for [math] i \in [n][/math] define a set-function [math]f_i[/math] on [math][n] \backslash \{i\}[/math] by [math]f_i(S) := f(S \cup \{i\})-f(S).[/math] Then equivalent conditions on b and p are that for all i, [math]b_i[/math] is monotonically nonincreasing, [math]p_i[/math] is monotonically nondecreasing, and [math]b_i(S) \ge p_i(T)[/math] 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
- [math]\{x \in \R^n \mid Ax\le b, Ax' \ge b'\} ~~~~~~ \textrm{where}~A~\textrm{and}~A'~\textrm{are 0-1 matrices}[/math]
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 [math]2^{[n]}[/math] 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
