|This article needs additional citations for verification. (February 2011) (Learn how and when to remove this template message)|
Consider any submodular set function on . Then define two associated polyhedra.
Here is called the polymatroid and is called the extended polymatroid associated with .
Relation to matroids
If f is integer-valued, 1-Lipschitz, and 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.
is nonempty if and only if and that is nonempty if and only if .
Given any extended polymatroid there is a unique submodular function such that and .
For a supermodular f one analogously may define the contrapolymatroid
- Edmonds, Jack. Submodular functions, matroids, and certain polyhedra. 1970. Combinatorial Structures and their Applications (Proc. Calgary Internat. Conf., Calgary, Alta., 1969) pp. 69–87 Gordon and Breach, New York. MR0270945
- Schrijver, Alexander (2003), Combinatorial Optimization, Springer, §44, p. 767, ISBN 3-540-44389-4
- Additional reading