Polymatroid

Definition

Consider any submodular set function f on E . Then define two associated polyhedra.

1. E P f := { x ∈ R E | ∑ e ∈ U x ( e ) ≤ f ( U ) , ∀ U ⊆ E }
2. P f := E P f ∩ { x ∈ R E | x ≥ 0 }

Here P f is called the polymatroid and E P f is called the extended polymatroid associated with f .

Relation to matroids

If f is integer-valued, 1-Lipschitz, and f ( ∅ ) = 0 then f is the rank-function of a matroid, and the polymatroid is the independent set polytope, so-called since Edmonds showed it is the convex hull of the characteristic vectors of all independent sets of the matroid.

Properties

P f is nonempty if and only if f ≥ 0 and that E P f is nonempty if and only if f ( ∅ ) ≥ 0 .

Given any extended polymatroid E P there is a unique submodular function f such that f ( ∅ ) = 0 and E P f = E P .

Contrapolymatroids

For a supermodular f one analogously may define the contrapolymatroid

This analogously generalizes the dominant of the spanning set polytope of matroids.