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: