The Partial Order of a Polymatroid Extreme Point

Abstract

Given a polymatroid rank function f and its corresponding polymatroid Pf, we associate with each extreme point of Pf a certain partial order. We show that this partial order is efficiently constructible, and that it characterizes all the orderings with which the greedy algorithm can be used to generate the given extreme point. We give several applications, including one to the still open problem of finding an efficient combinatorial procedure for testing membership in polymatroids. Our results can also be applied to convex games.