AN EXTREME POINT THEOREM FOR ORDERED POLYMATROIDS ON CHAIN ORDERS.pdf

AN EXTREME POINT THEOREM FOR ORDEREDPOLYMATROIDS ON CHAIN ORDERSULRICH KRUGERAbstract. We consider Ordered Polymatroids as a generalization ofpolymatroids and extend the extreme point characterization of polyma-troids by the greedy algorithm to the ordered case.It is proved that a feasible point of an Ordered Polymatroid is avertex i it is a Greedy-Vector with respect to an appropriate primalGreedy-Procedure.1. Introduction and NotationsIn [2] Faigle and Kern considered Submodular Linear Programs of thetype max Xe2E cexe(1) Xe2A+ xe  f(A) for all A 2 Awhere P = (E;) is a nite partially ordered set, c : E ! R a objectivefunction and f a submodular function with respect to a distributive latticeof ideals in P called A. An ideal of P is a subset I  E which satises theproperty e 2 A and f e =) f 2 A:Submodularity of f refers to the propertyf(A) + f(B)  f(A [B) + f(A \ B) for all A;B 2 Aas usually. The set of maximal elements of an ideal, say I , is denoted byI+. This notation is used forx(I+) := Xe2I+ xe:Later we easily write x+(I) instead of x(I+).We keep restricted to the special case A = 2(E;) troughout this paper,i.e. A consists of all ideals with respect to (E;). Then the polyhedronP(f) = fx : x(A)  f(A) for all A 2 2(E;)gDate: 2 April, 1996.1991 Mathematics Subject Classication. 90C27.Key words and phrases. greedy algorithm, polymatroid, poset, chain order.1 2 ULRICH KRUGERis called \Extended Ordered Polymatroid.Notice that P(f) describes the set of all feasible vectors of (1).The attribute \extended will be left if all feasible x are required to benon-negative, i.e. P+(f) := P(f)\R+denes an \Ordered Polymatroid. The name \Ordered Polymatroid is rea-sonable because ordinary polymatroids can easily be recognized as a subclassif P is assumed to be the trivial order. The reader is referred to Chapter10 of Grotschel, Lovasz, Schrijver [4, pp. 305-329] for a introduction intoPolymatroid-Theory and Submodular Functions.Faigle and Kern developed a prim