Re: [Haskell-cafe] Matroids in Haskell

On Fri, 14 Jan 2005, Michael Matsko wrote:

Dimitri

Matriods are generalization of vector spaces. Basically, they are defined by a set of linear dependence axioms and basis exchange properties. Oxley's "Matriod Theory" is the standard reference. There are a multitude of equivalent formulations.

... and the most spectacular result is, that a greedy algorithm for a problem is optimal if and only if the problem has Matroid structure.