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 $S$. Then define two associated polyhedra.

1. $P_f:=\{x\in \mathbb{R}^S|x\geq 0,x(U)\leq f(U)\}$ for each $U\subseteq S$
2. $EP_f:=\{x\in \mathbb{R}^S|x(U)\leq f(U)\}$ for each $U\subseteq S$

Here $P_f$ is called the polymatroid and $EP_f$ is called the extended polymatroid associated with $f$.

Properties

1. $P_f$ is nonempty if and only if $f\geq 0$ and that $EP_f$ is nonempty if and only if $f(\phi)\geq 0$
2. Given any extended polymatroid $EP$ there is a unique submodular function $f$ such that $f(\phi)=0$ and $EP_f=EP$
3. If r is integral, 1-Lipschitz, and $r(\varnothing)=0$ then r 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.
4. 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)\ge r(S)$

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

References

General References

• Schrijver, Alexander (2003), Combinatorial Optimization, Springer, ISBN 3540443894 
• Lee, Jon (2004), A First Course in Combinatorial Optimization, Cambridge University Press, ISBN 0521010128 
• Fujishige, Saruto (2005), Submodular Functions and Optimization, Elsevier, ISBN 0444520864 
• Narayanan, H. (1997), Submodular Functions and Electrical Networks, ISBN 0444825231