Séminaire Lotharingien de Combinatoire, B36f (1996), 8pp.

Ulrich Krüger

An extreme point theorem for ordered polymatroids on chain orders

Abstract. We consider ordered polymatroids as a generalization of polymatroids and extend the extreme point characterization of polymatroids by the greedy algorithm to the ordered case.
It is proved that a feasible point of an ordered polymatroid is a vertex iff it is a greedy-vector with respect to an appropriate primal greedy-procedure.

The following version is available: