Base polyhedron

Let V be a finite ground set, and let [math]b:2^V \to {\mathbb R} \cup \{\infty\}[/math] be a submodular function for which b(V) is finite and [math]b(\emptyset) = 0[/math]. The base polyhedron of b is

[math]B(b)=\{x \in {\mathbb R}^V: x(Z) \leq b(Z)\ \forall Z\subseteq V,\ x(V)=b(V)\}.[/math]

A base polyhedron defined this way is always nonempty. Moreover, if the finite values of b are integer, then B(b) is an integer polyhedron. If b is finite, then the polyhedron is bounded, and it is called a base polytope.

The same definition can be used for a crossing submodular function b. In this case, the polyhedron may be empty, and non-emptiness is characterized by Fujishige's base polyhedron theorem. However if it is non-empty, then there is a submodular function b' for which [math]B(b)=B(b')[/math].