Algorithms for optimization problems typically go through a sequence of steps, with a set of choices at each step. For many optimization problems, using dynamic programming to determine the best choices is overkill; simpler, more efficient algorithms will do. A * greedy algorithm* always makes the choice that looks best at the moment. That is, it makes a locally optimal choice in the hope that this choice will lead to a globally optimal solution. This chapter explores optimization problems that are solvable by greedy algorithms.

Our first example is the problem of scheduling a resource among several competing activities. We shall find that a greedy algorithm provides an elegant and simple method for selecting a maximum-size set of mutually compatible activities.

â_{1}â_{2}. . . â._{n}

GREEDY-ACTIVITY-SELECTOR(s, f)

1nlength[s]

2A{1}

3j1

4fori2ton

5doifsâ_{i}_{j}

6thenAA{i}

7ji

8returnA

â= max{_{j}f:_{k}KA}.

Give a dynamic-programming algorithm for the activity-selection problem, based on computing *m _{i}* iteratively for

Suppose that we have a set of activities to schedule among a large number of lecture halls. We wish to schedule all the activities using as few lecture halls as possible. Give an efficient greedy algorithm to determine which activity should use which lecture hall.

(This is also known as the * interval-graph coloring problem.* We can create an interval graph whose vertices are the given activities and whose edges connect incompatible activities. The smallest number of colors required to color every vertex so that no two adjacent vertices are given the same color corresponds to finding the fewest lecture halls needed to schedule all of the given activities.)

A greedy algorithm obtains an optimal solution to a problem by making a sequence of choices. For each decision point in the algorithm, the choice that seems best at the moment is chosen. This heuristic strategy does not always produce an optimal solution, but as we saw in the activity-selection problem, sometimes it does. This section discusses some of the general properties of greedy methods.

The first key ingredient is the * greedy-choice property*: a globally optimal solution can be arrived at by making a locally optimal (greedy) choice. Here is where greedy algorithms differ from dynamic programming. In dynamic programming, we make a choice at each step, but the choice may depend on the solutions to subproblems. In a greedy algorithm, we make whatever choice seems best at the moment and then solve the subproblems arising after the choice is made. The choice made by a greedy algorithm may depend on choices so far, but it cannot depend on any future choices or on the solutions to subproblems. Thus, unlike dynamic programming, which solves the subproblems bottom up, a greedy strategy usually progresses in a top-down fashion, making one greedy choice after another, iteratively reducing each given problem instance to a smaller one.

A problem exhibits * optimal substructure* if an optimal solution to the problem contains within it optimal solutions to subproblems. This property is a key ingredient of assessing the applicability of dynamic programming as well as greedy algorithms. As an example of optimal substructure, recall that the proof of Theorem 17.1 demonstrated that if an optimal solution

Because the optimal-substructure property is exploited by both greedy and dynamic-programming strategies, one might be tempted to generate a dynamic-programming solution to a problem when a greedy solution suffices, or one might mistakenly think that a greedy solution works when in fact a dynamic-programming solution is required. To illustrate the subtleties between the two techniques, let us investigate two variants of a classical optimization problem.

The * 0-1 knapsack problem* is posed as follows. A thief robbing a store finds

In the * fractional knapsack problem*, the setup is the same, but the thief can take fractions of items, rather than having to make a binary (0-1) choice for each item. You can think of an item in the 0-1 knapsack problem as being like a gold ingot, while an item in the fractional knapsack problem is more like gold dust.

Both knapsack problems exhibit the optimal-substructure property. For the 0-1 problem, consider the most valuable load that weighs at most *W *pounds. If we remove item *j* from this load, the remaining load must be the most valuable load weighing at most *W* - *w _{j}* that the thief can take from the

Although the problems are similar, the fractional knapsack problem is solvable by a greedy strategy, whereas the 0-1 problem is not. To solve the fractional problem, we first compute the value per pound *v _{i}*/

Prove that the fractional knapsack problem has the greedy-choice property.

Suppose that in a 0-1 knapsack problem, the order of the items when sorted by increasing weight is the same as their order when sorted by decreasing value. Give an efficient algorithm to find an optimal solution to this variant of the knapsack problem, and argue that your algorithm is correct.

Show how to solve the fractional knapsack problem in *O*(*n*) time. Assume that you have a solution to Problem 10-2.

Huffman codes are a widely used and very effective technique for compressing data; savings of 20% to 90% are typical, depending on the characteristics of the file being compressed. Huffman's greedy algorithm uses a table of the frequencies of occurrence of each character to build up an optimal way of representing each character as a binary string.

There are many ways to represent such a file of information. We consider the problem of designing a * binary character code* (or

a b c d e f

--------------------------------------------------------------

Frequency (in thousands) 45 13 12 16 9 5

Fixed-length codeword 000 001 010 011 100 101

Variable-length codeword 0 101 100 111 1101 1100

A* variable-length code* can do considerably better than a fixed-length code, by giving frequent characters short codewords and infrequent characters long codewords. Figure 17.3 shows such a code; here the 1-bit string 0 represents a, and the 4-bit string 1100 represents f. This code requires (45 1 + 13 3 + 12 3 + 16 3 + 9 4 + 5 4) 1,000 = 224,000 bits to represent the file, a savings of approximately 25%. In fact, this is an optimal character code for this file, as we shall see.

We consider here only codes in which no codeword is also a prefix of some other codeword. Such codes are called **prefix codes.**^{1} It is possible to show (although we won't do so here) that the optimal data compression achievable by a character code can always be achieved with a prefix code, so there is no loss of generality in restricting attention to prefix codes.

An optimal code for a file is always represented by a *full* binary tree, in which every nonleaf node has two children (see Exercise 17.3-1). The fixed-length code in our example is not optimal since its tree, shown in Figure 17.4(a), is not a full binary tree: there are codewords beginning 10 . . . , but none beginning 11 . . . . Since we can now restrict our attention to full binary trees, we can say that if *C* is the alphabet from which the characters are drawn, then the tree for an optimal prefix code has exactly *|C| leaves, one for each letter of the alphabet, and exactly |*C| - 1 internal nodes.

which we define as the * cost* of the tree

In the pseudocode that follows, we assume that *C* is a set of *n* characters and that each character *c* *C* is an object with a defined frequency *f*[*c*]. A priority queue *Q*, keyed on *f*, is used to identify the two least-frequent objects to merge together. The result of the merger of two objects is a new object whose frequency is the sum of the frequencies of the two objects that were merged.

HUFFMAN(C)

1n|C|

2 QC

3fori1ton -1

4dozALLOCATE-NODE()

5xleft[z] EXTRACT-MIN(Q)

6 yright[z] EXTRACT-MIN(Q)

7f[z]f[x] +f[y]

8 INSERT(Q,z)

9returnEXTRACT-MIN(Q)

To prove that the greedy algorithm HUFFMAN is correct, we show that the problem of determining an optimal prefix code exhibits the greedy-choice and optimal-substructure properties. The next lemma shows that the greedy-choice property holds.

Let *C* be an alphabet in which each character *c* *C* has frequency *f*[*c*]. Let *x* and *y* be two characters in *C* having the lowest frequencies. Then there exists an optimal prefix code for *C* in which the codewords for *x *and *y *have the same length and differ only in the last bit.

f[x]d(_{T}x) +f[y]d(_{T}y) = (f[x]) + (f[y])d'_{T}_{(z)}+ 1)

=f[z]d'_{T}_{(z)}+ (f[x] +f[y]),

B(T) =B(T') +f[x] +f[y].

Procedure HUFFMAN produces an optimal prefix code.

* Proof *Immediate from Lemmas 17.2 and 17.3.

Prove that a binary tree that is not full cannot correspond to an optimal prefix code.

a:1 b:1 c:2 d:3 e:5 f:8 g:13 h:21

2n- 1 +nlgn

There is a beautiful theory about greedy algorithms, which we sketch in this section. This theory is useful in determining when the greedy method yields optimal solutions. It involves combinatorial structures known as "matroids." Although this theory does not cover all cases for which a greedy method applies (for example, it does not cover the activity-selection problem of Section 17.1 or the Huffman coding problem of Section 17.3), it does cover many cases of practical interest. Furthermore, this theory is being rapidly developed and extended to cover many more applications; see the notes at the end of this chapter for references.

A * matroid* is an ordered pair satisfying the following conditions.

1. *S* is a finite nonempty set.

2. is a nonempty family of subsets of *S*, called the * independent* subsets of

3. If *,* and* |A| < |B|*, then there is some element *x* *B - A *such that . We say that *M *satisfies the * exchange property*.

The word "matroid" is due to Hassler Whitney. He was studying * matric matroids*, in which the elements of

As another illustration of matroids, consider the * graphic matroid* defined in terms of a given undirected graph

The set *S _{G}* is defined to be

The graphic matroid *M _{G}* is closely related to the minimum-spanning-tree problem, which is covered in detail in Chapter 24.

If* G* is an undirected graph, then is a matroid.

Given a matroid , we call an element *x* *A* an * extension* of if

If *A* is an independent subset in a matroid *M*, we say that *A* is * maximal *if it has no extensions. That is,

All maximal independent subsets in a matroid have the same size.

We say that a matroid is **weighted**** **if there is an associated 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:

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 , and we wish to find an independent set 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

For example, in the * minimum-spanning-tree problem*, we are given a connected undirected graph

w'(A)=(|V| - 1)ww_{0}-(A)

The elements of *S* are considered in turn, in order of nonincreasing 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 only added to *A *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.

We now prove that GREEDY returns an optima1 subset.

Suppose that is a weighted matroid with weight function *w* and that *S* is sorted into nonincreasing order by weight. Let *x* be the first element of *S* such that {*x*} is independent, if any such *x* exists. If *x* exists, then there exists an optimal subset *A* of *S* that contains *x*.

w(A)= w(B)- w(y) +w(x)

w(B) .

Because *B* is optimal, *A* must also be optimal, and because *x* *A*, the lemma is proven.

We next show that if an element is not an option initially, then it cannot be an option later.

Let *x* be the first element of *S* chosen by GREEDY for the weighted matroid . The remaining problem of finding a maximum-weight independent subset containing *x* reduces to finding a maximum-weight independent subset of the weighted matroid , where

An interesting problem that can be solved using matroids is the problem of optimally scheduling unit-time tasks on a single processor, where each task has a deadline and a penalty that must be paid if the deadline is missed. The problem looks complicated, but it can be solved in a surprisingly simple manner using a greedy algorithm.

a set *S* = {1, 2, . . . , *n*} of *n* unit-time tasks;

For any set of tasks *A*, the following statements are equivalent.

2. For *t* = 1, 2, . . . , *n*, we have *N _{t}*(

3. If the tasks in *A* are scheduled in order of nondecreasing deadlines, then no task is late.

Task

1 2 3 4 5 6 7

-------------------------------

d4 2 4 3 1 4 6_{i }

w70 60 50 40 30 20 10_{i }

2, 4, 1, 3, 7, 5, 6 ,

which has a total penalty incurred of *w*_{5 +}*w*_{6 = }50_{.}

Consider the problem of making change for *n* cents using the least number of coins*.*

**a****.** Let *G* = (*V, E*) be an undirected graph. Using the definition of a matroid, show that *) *is a matroid, where if and only if *A* is an acyclic subset of *E*.

* b.* The

* e.* The

Consider the following algorithm for solving the problem in Section 17.5 of scheduling unit-time tasks with deadlines and penalties. Let all *n* time slots be initially empty, where time slot *i* is the unit-length slot of time that finishes at time *i. *We consider the jobs in order of monotonically decreasing penalty. When considering job *j*, if there exists a time slot at or before* j*'s deadline *d _{j} *that is still empty, assign job

**a****.** Argue that this algorithm always gives an optional answer.

Much more material on greedy algorithms and matroids can be found in Lawler [132] and Papadimitriou and Steiglitz [154].