How to contact me.

Base *B*,
Circuit *C*,
Closure *s*,
Greedy *G*,
Independence *I*,
Rank *r*,
Rank *r'*.

# Greedy Algorithms

We recall the definition of an
*I-matroid*.

**Definition**.
An *I-matroid* (or, simply, *matroid*) *M=(S,I)*
is a finite set *S*,
together with a
collection *I* of subsets of *S* such that:

(i) *{ } ∈ I*;

(ii) if *Y ∈ I* and
*X ⊆ Y* then
*X ∈ I*; and

(iii) if *W*, *V ∈ I*,
with *|V| > |W|*, then there is some element
*z ∈ V \ W* for which
*W ∪ {z} ∈ I*.

The sets in *I* are called *independent sets*.
In more colloquial terms, the properties say:

(i) There is at least one independent set;

(ii) independence is an inherited property; and

(iii) we can augment a small independent set as
long as we know a larger
one.

We have already seen several examples of these matroids -
the two standard
examples being sets of vectors in *n*-space and
sets of edges in a graph with the
property that the edges contain no cycle.
For many of the theorems in matroid
theory, one should think about what the
theorem says about the two examples.

**Definition**.
A *weight function* for a matroid *M=(S,I)* is a
function *w* from *S* to the set of
non-negative real numbers.
We extend to subsets of *S* in the obvious fashion:

the weight of a subset is the sum of the
weights of the elements in the subset:
*w(A) = ∑ {w(x): x ∈ A}*.

Suppose that we have a matroid *M=(S,I)*,
together with a weight function.
A natural question arises:
"What is the maximum weight independent set?"
In general, there will be more than one such set.
Thus, one should ask for
"a maximum weight independent set."
The question of minimum weight independent sets
could also be considered - if
one restricts the consideration to those independent
sets which are of maximum cardinality.

A *greedy algorithm* proceeds by starting
with the empty set and
always grabbing an element which
gives the largest increase.

We can be more formal.

Let *S* be a finite set and
let *F* be a non-empty
family of subsets of *S* such that any subset
of any element of *F* is also in *F*.
We construct a finite
sequence *F*_{0}, F_{1}, ... of elements
from *F* by the rules:

(i) *F*_{0}={ };

(ii) for each integer *i ≥ 0*, let
*Z*_{i} = {z : z ∉ F_{i} and
*F*_{i} ∪ {z} ∈ F};

(iii) if *Z*_{i} = { }, terminate the algorithm;

(iv) if *Z*_{i} ≠ { },
pick an element *z*_{i} ∈ Z_{i} such that
*w(z*_{i}) ≥ w(z) for all *z* ∈ Z_{i},
set *F*_{i+1} = F_{i} ∪ {z_{i}},
and continue
(return to step (ii)).

**Theorem 1**.
If *F* is the set of independent sets of a matroid, then
the greedy algorithm constructs a
maximum weight element of *F*.

Proof.

**Theorem 2**.
If *F* is a non-empty collection of subsets of a
finite set *S* such that *F* is
closed under the subset operation and if
the greedy algorithm works for *(F,w)*,
for every weight function *w*, then *F* is the set of independent sets
of a matroid.

Proof.

We recall that condition (iii) in the
definition of a matroid forces all
maximal independent sets in a matroid to
be of the same cardinality.
A maximal independent set is called a
*base*,
just as in Matrix Theory.

**Proof of Theorem 1**.
Suppose the greedy algorithm
selects the base *B*.
Let *T* be a maximum weight base chosen to have
*|B ∩ T|*
as large as possible. If *B=T*, we are done.

Let *x* be the first element of *B \ T*
that is selected by the greedy
algorithm. Since *T* is a maximal independent set and
*x ∉ T*,
the set *T ∪ {x}* must be dependent.
Pick a minimal dependent subset *C* of
*T ∪ {x}*.
If *C ⊆ T*, then
*C* must be independent.
Hence *x ∈ C*.
Pick any element * y ∈ C \ B*.
Then *C \ {y}* is an independent set and
*C \ {y} ⊆ T ∪ {x}*.

Let *C*_{0} = C \ {y}. For each *i*,
*0 ≤ i < r = |T| − |C*_{0}|,
use axiom (iii) to find a
*z*_{i} ∈ T \ C_{i}
such that
*C*_{i+1} = C_{i} ∪ {z_{i}} is independent.
Finally set *T*_{1}=C_{r}.
We note that
*C \ {y} ⊆ T*_{1} ⊆ T ∪ {x},
*y ∉ T*_{1},
and *|T*_{1}| = |T|. Thus,
*T*_{1} = (T \ {y}) ∪ {x} is a base.

Now *T* was chosen to be a maximum weight independent set.
Thus *w(T*_{1}) ≤ w(T) and
*w(x) ≤ w(y)*.
On the other hand,
the greedy algorithm selected *x* but not *y*.
Let *X* denote the set of the elements
chosen by the greedy algorithm before *x* was chosen.
Then
*X ⊆ T*
and *X ∪ {y} ⊆ T*.
Hence *y* was available and
allowable at the time *x* was chosen.
Therefore,
*w(x) ≥ w(y)*.
This in turn forces *w(x) = w(y)* and
*w(T*_{1}) = w(T).
But now *T*_{1} is a maximum weight tree with
*|T*_{1} ∩ B| > |T ∩ B|,
contradicting the choice of *T*.

**Proof of Theorem 2**
The first two properties in the definition
of matroid are obviously satisfied by
*(S,F)*. We need check only the third.

Let *A* and *B* be elements of *F*
with *|A| < |B|*.
Let *t = |A ∩ B|*,
*k = |A \ B| = |A| - t*,
and
*r = |B| − |A| = |B| − t − k > 0*.
Define a weight function *w* on *S* by the rules

*w(e) = k+r+2* if *e ∈ A*

*w(e) = k+2* if *e ∈ B \ A*

*w(e) = 0* if *e ∉ A ∪ B*.

Apply the greedy algorithm to *(F,w)*.
The algorithm must first take
all of the elements of *A* and then
continue until it finds a maximum weight
element of *F*. But
*w(B) = t(k+r+2)+(k+r)(k+2) = t(k+r+2)+k(k+r+2)+2r = 2r+w(A) > w(A)*.
Therefore, the
greedy algorithm does not stop once it constructs *A*,
but must at the next
stage find an element *x ∉ A*
with *w(x) > 0*
and such that *A ∪ {x} ∈ F*.
However, the only elements with positive weight are in
*B ∪ A*.
Thus, *x ∈ B \ A*,
completing the proof.

**
Department of Mathematical Sciences**

Florida Atlantic University

777 Glades Road

Boca Raton, Florida 33431-0991

USA**
Office: Room 237, Science & Engineering**

Phone: (561) 297-3350

Fax: (561) 297-2436

URL: http://euler.math.fau.edu/locke/greedy.htm

Last modified January 30, 1996, by S.C. Locke. (Symbols updated March 10, 2014.)