Structural aspects of ordered polymatroids

This paper generalizes some aspects of polymatroid theory to partially orde red sets. The investigations are mainly based on Faigle and Kern (Math. Pro gramming 72 (1996) 195-206). A slightly modified concept of submodularity i s introduced. As a consequence many results do not require any assumptions concerning the underlying partially ordered groundset of the polymatroid. O ur modified concept of submodularity especially guarantees that the greedy algorithm works for arbitrary posets. We discuss the facial structure of or dered polymatroids and consider two different basis concepts. These are Cor e(f), the set of all elements with maximal component sum, and Max(f), the s et of all maximal feasible elements. Both concepts are equivalent for unord ered polymatroids. The sets Core(f) and Max(f) are completely described by inducing inequalities. Furthermore, it is shown by an example that Max(f) i s in general not a polyhedral set. Different ordered polymatroids may have the same core polytope. We will show that there is a unique smallest ordere d polymatroid in the set of all ordered polymatroids with the same core pol ytope. (C) 2000 Elsevier Science B.V. All rights reserved. MSC. 90C27; 52B1 2; 90C10; 05B35.