Polymatroid

From Wikipedia, the free encyclopedia
Jump to: navigation, search

In mathematics, polymatroid is a polytope associated with a submodular function. The notion was introduced by Jack Edmonds in 1970.[1]

Definition[edit]

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

Here is called the polymatroid and is called the extended polymatroid associated with .[2]

Relation to matroids[edit]

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.

Properties[edit]

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 .

Contrapolymatroids[edit]

For a supermodular f one analogously may define the contrapolymatroid

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

References[edit]

Footnotes
  1. ^ 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
  2. ^ Schrijver, Alexander (2003), Combinatorial Optimization, Springer, §44, p. 767, ISBN 3-540-44389-4 
Additional reading