On the geometric structure of independence systems

On the geometric structure of independence systems

0.00 Avg rating0 Votes
Article ID: iaor19891001
Country: Netherlands
Volume: 45
Issue: 2
Start Page Number: 255
End Page Number: 277
Publication Date: Oct 1989
Journal: Mathematical Programming
Authors: ,
Abstract:

A bouquet of matroids is a combinatorial structure that generalizes the properties of matroids. Given an independence system , there exist several bouquets of matroids having the same family of independent sets. The authors show that the collection of these geometries forms in general a meet semi-lattice and, in some cases, a lattice (for instance, when is the family of the stable sets in a graph). Moreover, one of the bouquets that correspond to the highest elements in the meet semi-lattice provides the smallest decomposition of into matroidal families, such that the rank functions of the different matroids have the same values for common sets. In the last section, they give sharp bounds on the performance of the greedy algorithm, using parameters of some special bouquets in the semi-lattice.

Reviews

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