Algorithms - greedy problems

The Greedy Algorithm
Tom Morgan, Jacob Steinhardt October 06, 2006

The Basics
The greedy algorithm is perhaps the most straightforward and powerful algorithm you will learn. The idea is simple: given a problem in which you are trying to minimize or maximize something and have some system you can operate on, you ask what the best thing you can do if you were to only do one. Next, you updatethe system and repeat.

When it works
The greedy algorithm can be used when a local change (as in taking the current best action) will not detrimentally affect the system as a whole. A classic example is as follows. Say you are low on funds and decide to rob a convenience store. To your misfortune you find that the convenience store has been robbed by another criminal moments before hand. As thestore now lacks any cash, you decide to steal and resell some of the store’s donuts. The store has a variety of donuts which each can be sold for different amounts. For example, they may have ten donuts that are worth $2 each, five that are worth $3 each and three that are worth $1 each. You have room for exactly seven donuts in your pack. What is the maximum amount of money you can make? The greedyapproach is to say: I have seven spots, what is the best donut I can pick for the first spot? I take it and repeat. This amounts to taking as many of the most valuable ones as possible and then moving on to the next most. We quickly find that the answer in this case is to take five $3 donuts and two $2 donuts.

When it doesn’t work
Taking the problem from before, it is no longer possible to solveif the donuts come in different sizes and we can not take fractions of donuts. For example if we have six spaces, and there is a donut of size four that is worth $8 and there are two donuts of size three that are worth $5 each. The greedy solution says to first take the $8 one but then we don’t have room for any more, while optimally we could fit the two $5 donuts for a total value of $10.Heuristics
The way in which the current best is evaluated is called a heuristic. Given the previous example (in which greedy doesn’t work) possible heuristics include: the donut worth the most, the donut that takes the least space and (most logically) the donut with the highest ratio of value to size. What can make greedy problems difficult is having complicated heuristics. When approaching a greedyproblem (or a problem you are trying to get partial credit on) do not be afraid to use multiple heuristics. By running multiple greedy algorithms and taking the best result, you can maximize your partial credit and on occasion simulate more complicated (and accurate) heuristics.

Advanced Techniques
There are many techniques for proving or deriving Greedy algorithms, each requiring various levels ofmathematical sophistication. Usually, we can show that a Greedy algorithm work if all choices are independent of each other. Additionally, if the swap of two elements enacts only a local change (that is, all other elements remain unaffected, or the total value remains unaffected), then a Greedy algorithm will also work. Additionally, the Greedy can be derived by writing an inequality that willdetermine when the second element should come after the first. Then, a sort should be performed using this criterion as the comparison method. This usually works (see below proof; it will work if a similar proof applies). Here is an example:

1

(US Open 2006) N cows go through a milking queue. The first part of the process takes Ai seconds for cow i, and the second part takes Bi seconds for cow i.Only one farmer is available for each part of the process, so it is feasible that the second farmer will be doing nothing while the first farmer is stuck milking a cow, or there can be a backup if the second farmer takes too long milking a cow (though the first farmer can continue milking). Determine in O(N logN ) time the minimum time it takes to milk al lthe cows. First note that the total time...