Polymatroid

In mathematics, the polymatroid defined by a given matroid $(E, r)$ is the set of all functions

$w:E\to\mathbb{R}$

such that

$w(e)\ge 0$

for all $e\in E$

$\sum_{e\in S}w(e)\le r(S)$

for all

$S\subseteq E\;$ .

Polymatroids are related to the convex polytopes seen in linear programming, and have similar uses.

The notion was introduced by Jack Edmonds in 1970. MR 0270945

This article incorporates material from polymatroid on PlanetMath, which is licensed under the GFDL.