The proof of the characterization results for base and bisubmodular polyhedra is inspired by similar characterizations for the optimality of classical greedy algorithms for linear optimization over these polyhedra [1]}, [2]}, [3]}. The latter characterizations state that for each permutation of the index set there exists a vector that simultaneously minimizes any linear cost function over these polyhedra whose coefficients are monotonically increasing or decreasing under this permutation. In this light, our characterization results can be seen as an extension of these classical results to convex objective functions.
