A general model for matroids and the greedy algorithm (Q1013980): Difference between revisions

The authors present a general model for matroid independence systems. The proposed model is based on the link between a family of subsets that includes the level set of the linear function to be optimized and a family of feasible solutions. The authors discuss the relationship between the proposed model of matroids and classical matroids. They show that the proposed model extends many of the models for generalized matroid-type greedy algorithms and, in particular, integral polymatroids. The authors introduce the notion of the base chain property and obtain a convenient framework for matroid duality. They discuss matroids that are defined with respect to closure and co-closure systems. The authors provide the construction of a Dilworth embedding and reduce matroids on distributive lattices of closed sets to the classical matroid theory.