Polymatroid

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

Definition

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

1. $EP_{f}:=\{x\in \mathbb {R} ^{E}|\sum _{e\in U}x(e)\leq f(U),\forall U\subseteq E\}$
2. $P_{f}:=EP_{f}\cap \{x\in \mathbb {R} ^{E}|x\geq 0\}$

Here $P_{f}$ is called the polymatroid and $EP_{f}$ is called the extended polymatroid associated with $f$.

Relation to matroids

If f is integer-valued, 1-Lipschitz, and $f(\emptyset )=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\geq 0$ and that $EP_{f}$ is nonempty if and only if $f(\emptyset )\geq 0$.

Given any extended polymatroid $EP$ there is a unique submodular function $f$ such that $f(\emptyset )=0$ and $EP_{f}=EP$.

Contrapolymatroids

For a supermodular f one analogously may define the contrapolymatroid

$w\in \mathbb {R} _{+}^{E}:\forall S\subseteq E,\sum _{e\in S}w(e)\geq f(S)$

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

References

Footnotes

Additional reading

• Lee, Jon (2004), A First Course in Combinatorial Optimization, Cambridge University Press, ISBN 0-521-01012-8
• Fujishige, Saruto (2005), Submodular Functions and Optimization, Elsevier, ISBN 0-444-52086-4
• Narayanan, H. (1997), Submodular Functions and Electrical Networks, ISBN 0-444-82523-1