Polymatroid

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 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.[2]

Properties

  1. 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
  2. Given any extended polymatroid EP there is a unique submodular function f such that f(\emptyset)=0 and EP_f=EP
  3. 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.
  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 f(S)
This analogously generalizes the dominant of the spanning set polytope of matroids.

Citations

<div class="reflist columns references-column-width" style="-moz-column-width: [1]; -webkit-column-width: [1]; column-width: [1]; list-style-type: decimal;">

  1. 1.0 1.1 1.2 1.3 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. MR 0270945
  2. (Schrijver 2003,§44, p. 767)

References

General References