Envelopes and clutters

Envelopes and clutters

0.00 Avg rating0 Votes
Article ID: iaor20013615
Country: Netherlands
Volume: 101
Issue: 1/3
Start Page Number: 177
End Page Number: 185
Publication Date: Apr 2000
Journal: Discrete Applied Mathematics
Authors: ,
Abstract:

In this paper, a set function ϕ defined on a finite set Ω is said to be an upper envelope if there exists a set {pi} of nonnegative vectors on Ω such that ϕ(G) = max {p1(G),…,pn(G)} for all G ⊂ Ω. All upper envelopes form a convex cone. We give a necessary and sufficient condition for an upper envelope to be extremal in the cone of all upper envelopes in terms of its representation. Furthermore we study the upper envelopes 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 connectivity.

Reviews

Required fields are marked *. Your email address will not be published.