In combinatorics, a branch of mathematics, a weighted matroid is a matroid endowed with a function that assigns a weight to each element.
for assigns a strictly positive weight to each element of
A basic problem regarding weighted matroids is to find an independent set with a maximum total weight.
This problem can be solved using the following simple greedy algorithm: This algorithm does not need to know anything about the matroid structure; it just needs an independence oracle for the matroid - a subroutine for testing whether a set is independent.
Jack Edmonds[1] proved that this simple algorithm indeed finds an independent set with maximum weight.
Denote the set found by the algorithm by e1,...,ek.
By the matroid properties, it is clear that k=rank(M), otherwise the set could be extended.
Assume by contradiction that there is another set with a higher weight.
Without loss of generality, it is possible to assume that this set has rank(M) elements too; denote it by f1,...,fk.
Apply the augmentation property to the sets {f1,...,fj} and {e1,...,ej-1}; we conclude that there must be some i ≤ j such that fi could be added to {e1,...,ej-1} while keeping it independent.
[2] As a simple example, say we wish to find the maximum spanning forest of a graph.
That is, given a graph and a weight for each edge, find a forest containing every vertex and maximizing the total weight of the edges in the tree.
This problem arises in some clustering applications.
If we look at the definition of the forest matroid, we see that the maximum spanning forest is simply the independent set with largest total weight — such a set must span the graph, for otherwise we can add edges without creating cycles.
There is a simple algorithm for finding a basis: The result is clearly an independent set.
is not independent either (the contrapositive follows from the hereditary property).
We will generalize this algorithm to solve a harder problem.
Optimal sets are always bases, because if an edge can be added, it should be; this only increases the total weight.
As it turns out, there is a trivial greedy algorithm for computing an optimal set of a weighted matroid.
It always chooses the element of largest weight that it can while preserving independence (thus the term "greedy").
is an element of maximal weight that can be added to
time using a comparison sorting algorithm.
If we want to find a minimum spanning tree instead, we simply "invert" the weight function by subtracting it from a large constant.
exceeds the total weight over all graph edges.
Many more optimization problems about all sorts of matroids and weight functions can be solved in this trivial way, although in many cases more efficient algorithms can be found that exploit more specialized properties.
of "independent" sets which is a down-set but not a matroid, then the greedy algorithm will not always work.
The greedy algorithm will select the elements of
This optimization algorithm may be used to characterize matroids: if a family F of sets, closed under taking subsets, has the property that, no matter how the sets are weighted, the greedy algorithm finds a maximum-weight set in the family, then F must be the family of independent sets of a matroid.
[3] The notion of matroid has been generalized to allow for other types of sets on which a greedy algorithm gives optimal solutions; see greedoid and matroid embedding for more information.
Korte and Lovász would generalize these ideas to objects called greedoids, which allow even larger classes of problems to be solved by greedy algorithms.