A general model for matroids and the greedy algorithm

U. Faigle, Saturo Fujishige

Research output: Contribution to journalArticleAcademic

11 Citations (Scopus)


We present a general model for set systems to be independence families with respect to set families which determine classes of proper weight functions on a ground set. Within this model, matroids arise from a natural subclass and can be characterized by the optimality of the greedy algorithm. This model includes and extends many of the models for generalized matroid-type greedy algorithms proposed in the literature and, in particular, integral polymatroids. We discuss the relationship between these general matroids and classical matroids and provide a Dilworth embedding that allows us to represent matroids with underlying partial order structures within classical matroids. Whether a similar representation is possible for matroids on convex geometries is an open question.
Original languageUndefined
Pages (from-to)353-369
JournalMathematical programming
Issue number2
Publication statusPublished - 2009


  • IR-79989

Cite this