Envelopes and clutters

Ln this paper, a set function cp defined on a finite set Omega is said to b e an upper envelope if there exists a set {pi} of nonnegative vectors on Om ega such that phi(G)= max{p(1)(G),. . . , p(n)(G)} for all G subset of a. A n upper envelopes form a convex cone. We give a necessary and sufficient co ndition for an upper envelope to be extremal in the cone of-all upper envel opes in terms of its representation. Furthermore we study the upper envelop es represented by clutters. We show that a clutter is extremal in the cone of the upper envelopes if and only if it satisfies some kind of connectivit y. (C) 2000 Elsevier Science B.V. All rights reserved.