Structural aspects of ordered polymatroids Original Research Article

This paper generalizes some aspects of polymatroid theory to partially ordered sets. The investigations are mainly based on Faigle and Kern (Math. Programming 72 (1996) 195–206). A slightly modified concept of submodularity is introduced. As a consequence many results do not require any assumptions concerning the underlying partially ordered groundset of the polymatroid. Our modified concept of submodularity especially guarantees that the greedy algorithm works for arbitrary posets. We discuss the facial structure of ordered polymatroids and consider two different basis concepts. These are Core(f), the set of all elements with maximal component sum, and Max(f), the set of all maximal feasible elements. Both concepts are equivalent for unordered polymatroids. The sets Core(f) and Max(f) are completely described by inducing inequalities. Furthermore, it is shown by an example that Max(f) is in general not a polyhedral set. Different ordered polymatroids may have the same core polytope. We will show that there is a unique smallest ordered polymatroid in the set of all ordered polymatroids with the same core polytope.