Fujishige's base polyhedron theorem
From Egres Open
Theorem (Fujishige [1]). Let [math]b:2^V \to {\mathbb R} \cup \{\infty\}[/math] be a crossing submodular function with [math]b(V) = b(\emptyset) = 0[/math]. Then the base polyhedron
[math]B(b)=\{x \in {\mathbb R}^V: x(Z) \leq b(Z)\ \forall Z\subseteq V,\ x(V)=b(V)\}[/math]
is non-empty if and only if
[math]\sum_{X \in P}b(X) \geq 0 \text{ and } \sum_{X \in P}b(V\setminus X) \geq 0[/math]
for every partition P of V. If the polyhedron is non-empty, then it is a base polyhedron.
