Finding a basis

There is a simple algorithm for finding a basis:

• Initially let ${\displaystyle A}$ be the empty set.
• For each ${\displaystyle x}$ in ${\displaystyle E}$
  • if ${\displaystyle A\cup \{x\}}$ is independent, then set ${\displaystyle A}$ to ${\displaystyle A\cup \{x\}}$.

The result is clearly an independent set. It is a maximal independent set because if ${\displaystyle B\cup \{x\}}$ is not independent for some subset ${\displaystyle B}$ of ${\displaystyle A}$, then ${\displaystyle A\cup \{x\}}$ is not independent either (the contrapositive follows from the hereditary property). Thus if we pass up an element, we'll never have an opportunity to use it later. We will generalize this algorithm to solve a harder problem.

Extension to optimal

An independent set of largest total weight is called an optimal set. 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 works as follows:

• Initially let ${\displaystyle A}$ be the empty set.
• For each ${\displaystyle x}$ in ${\displaystyle E}$, taken in (monotonically) decreasing order by weight
  • if ${\displaystyle A\cup \{x\}}$ is independent, then set ${\displaystyle A}$ to ${\displaystyle A\cup \{x\}}$.

This algorithm finds a basis, since it is a special case of the above algorithm. It always chooses the element of largest weight that it can while preserving independence (thus the term "greedy"). This always produces an optimal set: suppose that it produces ${\displaystyle A=\{e_{1},e_{2},\ldots ,e_{r}\}}$ and that ${\displaystyle B=\{f_{1},f_{2},\ldots ,f_{r}\}}$. Now for any ${\displaystyle k}$ with ${\displaystyle 1\leq k\leq r}$, consider open sets ${\displaystyle O_{1}=\{e_{1},\ldots ,e_{k-1}\}}$ and ${\displaystyle O_{2}=\{f_{1},\ldots ,f_{k}\}}$. Since ${\displaystyle O_{1}}$ is smaller than ${\displaystyle O_{2}}$, there is some element of ${\displaystyle O_{2}}$ which can be put into ${\displaystyle O_{1}}$ with the result still being independent. However ${\displaystyle e_{k}}$ is an element of maximal weight that can be added to ${\displaystyle O_{1}}$ to maintain independence. Thus ${\displaystyle e_{k}}$ is of no smaller weight than some element of ${\displaystyle O_{2}}$, and hence ${\displaystyle e_{k}}$ is of at least a large a weight as ${\displaystyle f_{k}}$. As this is true for all ${\displaystyle k}$, ${\displaystyle A}$ is weightier than ${\displaystyle B}$.

Complexity analysis

The easiest way to traverse the members of ${\displaystyle E}$ in the desired order is to sort them. This requires ${\displaystyle O(|E|\log |E|)}$ time using a comparison sorting algorithm. We also need to test for each ${\displaystyle x}$ whether ${\displaystyle A\cup \{x\}}$ is independent; assuming independence tests require ${\displaystyle O(f(|E|))}$ time, the total time for the algorithm is ${\displaystyle O(|E|\log |E|+|E|f(|E|))}$.

If we want to find a minimum spanning tree instead, we simply "invert" the weight function by subtracting it from a large constant. More specifically, let ${\displaystyle w_{\text{min}}(x)=W-w(x)}$, where ${\displaystyle W}$ 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.

Matroid requirement

Note also that if we take a set ${\displaystyle I}$ of "independent" sets which is a down-set but not a matroid, then the greedy algorithm will not always work. For then there are independent sets ${\displaystyle I_{1}}$ and ${\displaystyle I_{2}}$ with ${\displaystyle |I_{1}|<|I_{2}|}$, but such that for no ${\displaystyle e\in I_{2}\setminus I_{1}}$ is ${\displaystyle I_{1}\cup e}$ independent.

Pick an ${\displaystyle \epsilon >0}$ and ${\displaystyle \tau >0}$ such that ${\displaystyle (1+2\epsilon )|I_{1}|+\tau |E|<|I_{2}|}$. Weight the elements of ${\displaystyle I_{1}\cup I_{2}}$ in the range ${\displaystyle 2}$ to ${\displaystyle 2+2\epsilon }$, the elements of ${\displaystyle I_{1}\setminus I_{2}}$ in the range ${\displaystyle 1+\epsilon }$ to ${\displaystyle 1+2\epsilon }$, the elements of ${\displaystyle I_{2}\setminus I_{1}}$ in the range ${\displaystyle 1}$ to ${\displaystyle 1+\epsilon }$, and the rest in the range ${\displaystyle 0}$ to ${\displaystyle \tau }$. The greedy algorithm will select the elements of ${\displaystyle I_{1}}$, and then cannot pick any elements of ${\displaystyle I_{2}\setminus I_{1}}$. Therefore, the independent set it constructs will be of weight at most ${\displaystyle (1+2\epsilon )|I_{1}|+\tau |E|+|I_{1}\cup I_{2}|}$, which is smaller than the weight of ${\displaystyle I_{2}}$.