Greedy

A greedy solution is one where we can make every decision in the course of our algorithm based on some simple rule. To put it a bit more precisely, a greedy algorithm has the property that the locally optimal solution to any sub-problem will lead to a globally optimal solution.

Examples

• Making Change in fewest number of coins
  • Select the highest value coin with value no greater than the amount of change you have remaining to make (true with most real currencies, but not in general)
  • The locally optimal solution (choosing the coin with the highest value) will lead to the globally optimal solution (fewest coins)
• Task Scheduling to complete tasks by deadlines
  • If you are trying to figure out if you can get a bunch of tasks each with their individual deadline done on time, always work on the one with the earliest deadline first
  • The locally optimal solution (choosing the earliest deadline) will lead to the globally optimal solution (each task getting done (hopefully) before its deadline)
• knapsack with partial items
  • if you have a maximum weight to carry and want to maximize value (and can take fractions of an item), obviously you take items with highest value-to-weight first
  • The locally optimal solution (choosing your next item based on value/weight ratio) leads to the globally optimal solution (highest total value for a given weight)
• [Minimum Spanning Tree]

Recognizing Greedy Problems

Identifying greedy problems is something that is very easy to get wrong. Often new students will think a greedy solution is optimal, but will not have considered corner cases. This leads to coming up with more and more convoluted rules to apply as your greedy metric, and eventually it becomes very difficult to come up with a counter example. The answer will still end up being wrong, though.

In any case, there are several hints that a problem might be greedy

1. The algorithm involves decision making. You have to choose some item, or path. It should be noted that this only narrows the solution space to a few classes of algorithms, once you have a decision problem, you should see if you can come up with a greedy metric
2. You can prove a greedy solution is correct (see below)
3. There is some sort of diminishing returns. For instance if you can take multiple of an item, and each time, the value of the next of that item goes down, it's a strong hint that there is a greedy component to the solution.
4. Choices don't come with "strings attached". For instance, if you consider the scheduling problem above, and there was some strange rules about being forced to only work on some tasks before others, or only at certain times, it's a strong hint that it's NOT greedy. The big exception to this "hint" (not a hard and fast rule), is the bit about diminishing returns above.

So now the only thing that should be clear is that there is no sure way to recognize greedy problems. The best you can do is see if you can come up with a greedy solution and see if it works

Deciding if a Greedy Solution is Correct

So you think a problem MIGHT be a greedy problem, and you've come up with some greedy rule you think is right.

STOP!

you might be wrong.

The unfortunate about greedy is that it's one of the first techniques taught. Therefore students always try to fit the square greedy peg into the round problem hole. No matter how much you try to squish it, it's not going to work. Here's perhaps the hardest and fastest rule on greedy:

The more complicated your rule is, the more likely it is to be wrong.

So if you have some crazy rule with all sorts of exceptions, it's probably wrong.

Okay, so you still think your answer might be right...fine. The next steps you should take:

1. Can I prove this is correct? Most of the time you don't actually need to do this, but if you CAN, you might as well, and then skip the rest. More on this below
2. Can I think of a counter example? Think in earnest. Try to find any situation where your rule would fail. If you can even imagine a plausible situation where your rule might fail, even if you can't piece together the exact case, it's probably wrong. And don't even think about saying "oh the judges won't have done that"....they will have. and you will have a wrong answer and 20 minute time penalty. This is the technique I probably use most often, as even just vaguely imagining some sort of situation where it might fail is usually enough. Given sometimes you come back to greedy if all your other techniques failed too...so be it.
3. Remember that "proof by lack of counter example" is not really a proof, and so ask your teammates if THEY can poke any holes in your solution
4. See if you can recall any other similar problem which has a greedy solution

If you get through all those steps, congratulations, you MIGHT have a greedy solution. Code it up and submit it.

Proving a Greedy Solution

Greedy proofs almost always take the form of a proof by contradiction: we assume there is some exception to our rule, and then demonstrate why this can't be the case. Take the scheduling problem from above for example

• Suppose there was an optimal solution where we chose a later deadline first
• The total time taken to complete the two tasks is still the same, despite the swap
• the later deadline must be later than the the combined time of the two tasks, in both cases
• The earlier deadline now must be later than the combined time of the two tasks, despite only having to be later than the time of task A before
• Since we have fewer combinations of deadlines for which this schedule will succeed, the solution is less optimal, violating our initial assumption

Walking through a Greedy Solution

Lets consider Have You Driven a Fjord Lately: pdf

This problem asks us where to build bridges to save the greatest distance. Asked a different way, how do we allocate the m meters of bridge to the individual fjords to get the most savings?

My thought process goes like this

1. Since for every meter of bridge, we have to choose which fjord to build it at, this is definitely a decision problem, so greedy is definitely a candidate
2. All sections of bridge are equal it doesn't cost more to build a longer bridge, which is one less restriction, and at least keeps greedy viable
3. This would be pretty easy if all the fjords were isosceles...we could just build the longest bridges on the narrowest fjords! since that will get us the most savings because...math!
   • Does this cause an issue because we have to go in single meter segments? Boundary effects? No. It's still best to build the longest bridge since the savings is constant for a given fjord angle
4. So how do we deal with the non-isosceles fjords? Obviously we'll build it as if it were isosceles until we get to one endpoint, but what after then?
5. well, if we continue to build out, we'll have diminishing returns, so each extra meter of bridge gets us less savings than the previous (you can see this with MATH
   • Hmm...diminishing returns...could be greedy!
6. what if i just try adding 1 meter of extra bridge to each fjord, and actually add it to the one that would yield the most savings?
   • we know this works for both isosceles portions and the non-isosceles portions....so it SHOULD work for all
7. Can I prove this?
   • yes...but lets skip it for now
8. Can I imagine a situation where this DOESN'T work?
   • no
9. Is it a simple rule
   • yes
10. Hey Bo, do you think this is right?
    • seems like it to me

So that's the answer. We saw that there were no funky interactions between decisions and that the payoff either stays the same or diminishes, so greedy is probably right!

What to do when Greedy Fails

So when your greedy solution probably isn't right, where do you look next? Almost invariably, it's Dynamic Programming, so consider that next.

More Reading

https://www.topcoder.com/community/data-science/data-science-tutorials/greedy-is-good/