Generalized polymatroid

From Egres Open
Jump to: navigation, search

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


  1. 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. 2.0 2.1 Frank, A. and Tardos, É. Generalized polymatroids and submodular flows, Mathematical Programming 42(1):489–563, 1988. DOI link, author link
  3. S. Fujishige, A note on Frank's generalized polymatroids, Discrete Applied Mathematics 7 105n‐109, 1984. DOI link
  4. A. Frank, T. Király, J. Pap, D. Pritchard, Characterizing and recognizing generalized polymatroids, DOI link, EGRES Technical Report.
  5. T. Király, Base polyhedra and the linking property, EGRES Technical Report no. 2016-06
  6. Schrijver, A. Combinatorial Optimization, section 49.11b. Springer, 2003.
  7. 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