In mathematics, a polymatroid is a polytope associated with a submodular function. The notion was introduced by Jack Edmonds in 1970. It is also a generalization of the notion of a matroid.
Definition
Polyhedral definition Let E {\displaystyle E} be a finite set and f : 2 E → R ≥ 0 {\displaystyle f:2^{E}\rightarrow \mathbb {R} _{\geq 0}} a non-decreasing submodular function, that is, for each A ⊆ B ⊆ E {\displaystyle A\subseteq B\subseteq E} we have f ( A ) ≤ f ( B ) {\displaystyle f(A)\leq f(B)} , and for each A , B ⊆ E {\displaystyle A,B\subseteq E} we have f ( A ) + f ( B ) ≥ f ( A ∪ B ) + f ( A ∩ B ) {\displaystyle f(A)+f(B)\geq f(A\cup B)+f(A\cap B)} . We define the polymatroid associated to f {\displaystyle f} to be the following polytope:
P f = { x ∈ R ≥ 0 E | ∑ e ∈ U x ( e ) ≤ f ( U ) , ∀ U ⊆ E } {\displaystyle P_{f}={\Big \{}{\textbf {x}}\in \mathbb {R} _{\geq 0}^{E}~{\Big |}~\sum _{e\in U}{\textbf {x}}(e)\leq f(U),\forall U\subseteq E{\Big \}}} . When we allow the entries of x {\displaystyle {\textbf {x}}} to be negative we denote this polytope by E P f {\displaystyle EP_{f}} , and call it the extended polymatroid associated to f {\displaystyle f} .
Matroidal definition In matroid theory, polymatroids are defined as the pair consisting of the set and the function as in the above definition. That is, a polymatroid is a pair ( E , f ) {\displaystyle (E,f)} where E {\displaystyle E} is a finite set and f : 2 E → R ≥ 0 {\displaystyle f:2^{E}\rightarrow \mathbb {R} _{\geq 0}} , or Z ≥ 0 , {\displaystyle \mathbb {Z} _{\geq 0},} is a non-decreasing submodular function. If the codomain is Z ≥ 0 , {\displaystyle \mathbb {Z} _{\geq 0},} we say that ( E , f ) {\displaystyle (E,f)} is an integer polymatroid. We call E {\displaystyle E} the ground set and f {\displaystyle f} the rank function of the polymatroid. This definition generalizes the definition of a matroid in terms of its rank function. A vector x ∈ R ≥ 0 E {\displaystyle x\in \mathbb {R} _{\geq 0}^{E}} is independent if ∑ e ∈ U x ( e ) ≤ f ( U ) {\displaystyle \sum _{e\in U}x(e)\leq f(U)} for all U ⊆ E {\displaystyle U\subseteq E} . Let P {\displaystyle P} denote the set of independent vectors. Then P {\displaystyle P} is the polytope in the previous definition, called the independence polytope of the polymatroid. Under this definition, a matroid is a special case of integer polymatroid. While the rank of an element in a matroid can be either 0 {\displaystyle 0} or 1 {\displaystyle 1} , the rank of an element in a polymatroid can be any nonnegative real number, or nonnegative integer in the case of an integer polymatroid. In this sense, a polymatroid can be considered a multiset analogue of a matroid.
… excerpt ends here. Continue reading the full article.
