Data.Matroid.Algorithms.Greedy

Description

This module provides implementations of the greedy algorithm for optimization on matroids.

Synopsis

Documentation

Arguments

:: Matroid m a
=> m a	matroid to optimize on
-> [a]	elements of the groundset of the matroid, ordered from the best (most revenue, least cost, ...) element to the worst yet still improving element
-> Set a

Obtains an independent set of the given matroid that is optimal wrt. some optimization problem.

This version uses a ranking of the benefits of the elements of the groundset and the indep function in order to obtain an optimal result.

Arguments

:: Matroid m a
=> m a	matroid to optimize on
-> (Set a -> Maybe a)	picks the best element from the set, or nothing if adding an element would result in a worse outcome
-> Set a

Obtains an independent set of the given matroid that is optimal wrt. some optimization problem.

This version uses a choice function that selects the best element from a list of allowed choices, or Nothing to stop the process.