Chapter 4 Greedy Algorithms In Wall Street that iconic movie of the 1980s Michael Douglas gets up in front of a room full of stockholders and proclaims Greed is good Greed is right Greed works In this chapter we ll be taking a much more understated perspective as we investigate the pros and cons of short sighted greed in the design of algorithms Indeed our aim is to approach a number of different computational problems with a recurring set of questions Is greed good Does greed work It is hard if not impossible to de ne precisely what is meant by a greedy algorithm An algorithm is greedy if it builds up a solution in small steps choosing a decision at each step myopically to optimize some underlying criterion One can often design many different greedy algorithms for the same problem each one locally incrementally optimizing some different measure on its way to a solution When a greedy algorithm succeeds in solving a nontrivial problem opti mally it typically implies something interesting and useful about the structure of the problem itself there is a local decision rule that one can use to con struct optimal solutions And as we ll see later in Chapter 11 the same is true of problems in which a greedy algorithm can produce a solution that is guar anteed to be close to optimal even if it does not achieve the precise optimum These are the kinds of issues we ll be dealing with in this chapter It s easy to invent greedy algorithms for almost any problem nding cases in which they work well and proving that they work well is the interesting challenge The rst two sections of this chapter will develop two basic methods for proving that a greedy algorithm produces an optimal solution to a problem One can view the rst approach as establishing that the greedy algorithm stays ahead By this we mean that if one measures the greedy algorithm s progress 116 Chapter 4 Greedy Algorithms in a step by step fashion one sees that it does better than any other algorithm at each step it then follows that it produces an optimal solution The second approach is known as an exchange argument and it is more general one considers any possible solution to the problem and gradually transforms it into the solution found by the greedy algorithm without hurting its quality Again it will follow that the greedy algorithm must have found a solution that is at least as good as any other solution Following our introduction of these two styles of analysis we focus on several of the most well known applications of greedy algorithms shortest paths in a graph the Minimum Spanning Tree Problem and the construc tion of Huffman codes for performing data compression They each provide nice examples of our analysis techniques We also explore an interesting re lationship between minimum spanning trees and the long studied problem of clustering Finally we consider a more complex application the Minimum Cost Arborescence Problem which further extends our notion of what a greedy algorithm is 4 1 Interval Scheduling The Greedy Algorithm Stays Ahead Let s recall the Interval Scheduling Problem which was the rst of the ve representative problems we considered in Chapter 1 We have a set of requests 1 2 n the ith request corresponds to an interval of time starting at s i and nishing at f i Note that we are slightly changing the notation from Section 1 2 where we used si rather than s i and fi rather than f i This change of notation will make things easier to talk about in the proofs We ll say that a subset of the requests is compatible if no two of them overlap in time and our goal is to accept as large a compatible subset as possible Compatible sets of maximum size will be called optimal Designing a Greedy Algorithm Using the Interval Scheduling Problem we can make our discussion of greedy algorithms much more concrete The basic idea in a greedy algorithm for interval scheduling is to use a simple rule to select a rst request i1 Once a request i1 is accepted we reject all requests that are not compatible with i1 We then select the next request i2 to be accepted and again reject all requests that are not compatible with i2 We continue in this fashion until we run out of requests The challenge in designing a good greedy algorithm is in deciding which simple rule to use for the selection and there are many natural rules for this problem that do not give good solutions Let s try to think of some of the most natural rules and see how they work 4 1 Interval Scheduling The Greedy Algorithm Stays Ahead 117 The most obvious rule might be to always select the available request that starts earliest that is the one with minimal start time s i This way our resource starts being used as quickly as possible This method does not yield an optimal solution If the earliest request i is for a very long interval then by accepting request i we may have to reject a lot of requests for shorter time intervals Since our goal is to satisfy as many requests as possible we will end up with a suboptimal solution In a really bad case say when the nish time f i is the maximum among all requests the accepted request i keeps our resource occupied for the whole time In this case our greedy method would accept a single request while the optimal solution could accept many Such a situation is depicted in Figure 4 1 a This might suggest that we should start out by accepting the request that requires the smallest interval of time namely the request for which f i s i is as small as possible As it turns out this is a somewhat better rule than the previous one but it still can produce a suboptimal schedule For example in Figure 4 1 b accepting the short interval in the middle would prevent us from accepting the other two which form an optimal solution a b c Figure 4 1 Some instances of the Interval Scheduling Problem on which natural greedy algorithms fail to find the optimal solution In a it does not work to select the interval that starts earliest in b it does not work to select the shortest interval and in c it does not work to select the interval with the fewest conflicts 118 Chapter 4 Greedy Algorithms In the previous greedy rule our problem was that the second request competes with both the rst and the third that is accepting this request made us reject two other requests We could design a greedy algorithm that is based on this idea for each request we count the number of other requests that are not compatible and accept the request that has the fewest number of
View Full Document
Unlocking...