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₀, F₁, ... of elements from F by the rules:

(i) F₀={ };
(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₀ = C \ {y}. For each i, 0 ≤ i < r = |T| − |C₀|, 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₁=C_r. We note that C \ {y} ⊆ T₁ ⊆ T ∪ {x}, y ∉ T₁, and |T₁| = |T|. Thus, T₁ = (T \ {y}) ∪ {x} is a base.

Now T was chosen to be a maximum weight independent set. Thus w(T₁) ≤ 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₁) = w(T). But now T₁ is a maximum weight tree with |T₁ ∩ 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 Building
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.)