Jump to content

Polymatroid

From Wikipedia, the free encyclopedia

This is an old revision of this page, as edited by David Eppstein (talk | contribs) at 18:15, 7 September 2015 (more sections). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

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

Definition

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

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

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

For a supermodular f one analogously may define the contrapolymatroid

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

References

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