Data.Matroid.Algorithms.Greedy

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

Documentation

greedy

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.

greedy1

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.