Polymatroid

In mathematics, a polymatroid is a polytope associated with a submodular function. The notion was introduced by Jack Edmonds in 1970. It is also described as the multiset analogue of the matroid. In mathematics, a polymatroid is a polytope associated with a submodular function. The notion was introduced by Jack Edmonds in 1970. It is also described as the multiset analogue of the matroid. Let E {displaystyle E} be a finite set and f : 2 E → R + {displaystyle f:2^{E} ightarrow mathbb {R} _{+}} a non-decreasing submodular function, that is, for every A ⊂ B ⊂ E {displaystyle Asubset Bsubset E} we have f ( A ) ≤ f ( B ) {displaystyle f(A)leq f(B)} , and f ( A ) + f ( B ) ≥ f ( A ∪ B ) + f ( A ∩ B ) {displaystyle f(A)+f(B)geq f(Acup B)+f(Acap B)} . We define the polymatroid associated to f {displaystyle f} to be the following polytope: P f := { x ∈ R + E   |   ∑ e ∈ U x ( e ) ≤ f ( U ) , ∀ U ⊆ E } {displaystyle P_{f}:=left{{ extbf {x}}in mathbb {R} _{+}^{E}~|~sum _{ein U}{ extbf {x}}(e)leq f(U),forall Usubseteq E ight}} . When we allow the entries of x {displaystyle { extbf {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} . Let E {displaystyle E} be a finite set and u , v ∈ R E {displaystyle { extbf {u}},{ extbf {v}}in mathbb {R} ^{E}} . We call the modulus of u {displaystyle { extbf {u}}} to be the sum of all of its entries, and denote u ≤ v {displaystyle { extbf {u}}leq { extbf {v}}} whenever v i − u i ≥ 0 {displaystyle v_{i}-u_{i}geq 0} for every i ∈ E {displaystyle iin E} (notice that this gives an order to R + E {displaystyle mathbb {R} _{+}^{E}} ). A polymatroid on the ground set E {displaystyle E} is a nonempty compact subset P {displaystyle P} in R + E {displaystyle mathbb {R} _{+}^{E}} , the set of independent vectors, such that: This definition is equivalent to the one described before, where f {displaystyle f} is the function defined by f ( A ) = max { ∑ i ∈ A v ( i )   |   v ∈ P } {displaystyle f(A)=max left{sum _{iin A}{ extbf {v}}(i)~|~{ extbf {v}}in P ight}} for every A ⊂ E {displaystyle Asubset E} . To every matroid M {displaystyle M} on the ground set E {displaystyle E} we can associate the set P M = { w F   |   F ∈ M } {displaystyle P_{M}={{ extbf {w}}_{F}~|~Fin M}} , where for every i ∈ E {displaystyle iin E} we have that w F ( i ) = { 1 , i ∈ F ; 0 , i ∉ F . {displaystyle { extbf {w}}_{F}(i)={egin{cases}1,&iin F;\0,&i ot in F.end{cases}}} By taking the convex hull of P M {displaystyle P_{M}} we get a polymatroid, in the sense of the second definition, associated to the rank function of M {displaystyle M} .