Matroids and greedy methods

 Matroids and greedy methods

Matroids were first described in 1935 by the mathematician Hassler Whitney as a combinatorial generalization of linear independence of vectors—‘matroid’ means ‘something sort of like a matrix’.

Many problems that can be correctly solved by greedy algorithms can be described in terms of an abstract combinatorial object called a matroid.

In terms of independence, a finite matroid ${\displaystyle M}$ has following properties:

1. The empty set is independent, i.e., ${\displaystyle \emptyset \in {\mathcal {I}}}$. Alternatively, at least one subset of ${\displaystyle E}$ is independent, i.e., ${\displaystyle {\mathcal {I}}\neq \emptyset }$.
2. Every subset of an independent set is independent, i.e., for each ${\displaystyle A'\subseteq A\subseteq E}$, if ${\displaystyle A\in {\mathcal {I}}}$ then ${\displaystyle A'\in {\mathcal {I}}}$. This is sometimes called the hereditary property.
3. If ${\displaystyle A}$ and ${\displaystyle B}$ are two independent sets (i.e., each set is independent) and ${\displaystyle A}$ has more elements than ${\displaystyle B}$, then there exists ${\displaystyle x\in A\backslash B}$ such that ${\displaystyle B\cup \{x\}}$ is in ${\displaystyle {\mathcal {I}}}$. This is sometimes called the augmentation property or the independent set exchange property.
4. 
   

5. If A is an independent subset in a matroid M, we say that A is maximal if it has no extensions. That is, A is maximal if it is not contained in any larger independent subset of M. The following property is often useful. All maximal independent subsets in a matroid have the same size.

Weighted matriod:

A matroid is weighted if it is associated with a weight function w that assigns a strictly positive weight w(x) to each element x Є S. The weight function w extends to subsets of S by summation:

 for any 

Greedy algorithms on a weighted matroid

Theorem: ( Correctness of the greedy algorithm on matroids)

Many problems for which a greedy approach provides optimal solutions can be formulated in terms of finding a maximum-weight independent subset in a weighted matroid.

Given a weighted matroid , and to find an independent set A such that w(A) is maximized can be done by following algorithm.

The algorithm takes as input a weighted matroid with an associated positive weight function w, and it returns an optimal subset A. The algorithm is greedy because it considers in turn each element x Є S, in order of monotonically decreasing weight, and immediately adds it to the set A being accumulated if  is independent. The entire algorithm runs in time O(n lg n + n f (n)).

Example: