Theoretical Foundations For Greedy Methods

Greedy algorithms on a weighted matroid

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. That is, we are given a weighted matroid M = (S,ℓ), and we wish to find an independent set A ∈ℓ such that w(A) is maximized. We call such a subset that is independent and has maximum possible weight an optimal subset of the matroid. Because the weight w(x) of any element x ∈ S is positive, an optimal subset is always a maximal independent subset-it always helps to make A as large as possible.

For example, in the minimum-spanning-tree problem, we are given a connected undirected graph G = (V, E) and a length function w such that w(e) is the (positive) length of edge e. (We use the term "length" here to refer to the original edge weights for the graph, reserving the term "weight" to refer to the weights in the associated matroid.) We are asked to find a subset of the edges that connects all of the vertices together and has minimum total length. To view this as a problem of finding an optimal subset of a matroid, consider the weighted matroid M_G with weight function w′, where w′(e) = w₀ - w(e) and w₀ is larger than the maximum length of any edge. In this weighted matroid, all weights are positive and an optimal subset is a spanning tree of minimum total length in the original graph. More specifically, each maximal independent subset A corresponds to a spanning tree, and since

w′(A) = (|V| - 1)w₀ - w(A)

for any maximal independent subset A, an independent subset that maximizes the quantity w′(A) must minimize w(A). Thus, any algorithm that can find an optimal subset A in an arbitrary matroid can solve the minimum-spanning-tree problem.

Chapter 23 gives algorithms for the minimum-spanning-tree problem, but here we give a greedy algorithm that works for any weighted matroid. The algorithm takes as input a weighted matroid M = (S,ℓ) with an associated positive weight function w, and it returns an optimal subset A. In our pseudocode, we denote the components of M by S[M] andℓ[M] and the weight function by w. The algorithm is greedy because it considers each element x ∈ S in turn in order of monotonically decreasing weight and immediately adds it to the set A being accumulated if A∪{x} is independent.

	GREEDY(M, w)
1  A ← Ø
2  sort S[M] into monotonically decreasing order by weight w
3  for each x S[M], taken in monotonically decreasing order by weight w(x)
4       do if A ∪ {x} ∈ℓ[M]
5             then A ← A ∪ {x}
6  return A

The elements of S are considered in turn, in order of monotonically decreasing weight. If the element x being considered can be added to A while maintaining A's independence, it is. Otherwise, x is discarded. Since the empty set is independent by the definition of a matroid, and since x is added to A only if A ∪ {x} is independent, the subset A is always independent, by induction. Therefore, GREEDY always returns an independent subset A. We shall see in a moment that A is a subset of maximum possible weight, so that A is an optimal subset.

The running time of GREEDY is easy to analyze. Let n denote |S|. The sorting phase of GREEDY takes time O(n lg n). Line 4 is executed exactly n times, once for each element of S. Each execution of line 4 requires a check on whether or not the set A ∪ {x} is independent. If each such check takes time O(f(n)), the entire algorithm runs in time O(n lg n nf (n)).

We now prove that GREEDY returns an optimal subset.