What’s The Greedy Algorithm?

Many people instinctively use a greedy algorithm to solve problems, but they should have no expectation that it will generate optimal or even good results.

By: Don Shaughnessy

Back in the depths of history, I took a course in operations research.  Essentially the process of applying mathematical analysis to real world problems.  One of the interesting parts was the Greedy Algorithm.  It is the process where you choose the most expedient next step without consideration of other possible solutions or even how you got to where you are.

Some (even most) possible courses of action can thus never be implemented because the first step is not as good.  The greedy algorithm can perpetuate or even create problems.

For those with short time frames, it’s attractive.  “We are going to do this now and we will deal with any problems that arise, if and when they arise.”  Bias to action.  Sometimes they say it even when the future problem is known and certain to occur.

Micromanaging is an indicator.  You can make all the decisions if you only think one step at a time.

The algorithm can sometimes generate the unique, worst-possible, answer.  The “traveling salesman” problem where you are to find the best way to visit a list of customers is one. Take the closest next seems obvious, but that choice will always generate the worst route.

When the algorithm fails, it is because an early right looking step was wrong.  People tend not to go back and restart.  Often that choice is unavailable.  Lovers of greedy usually attack the newly observed problem in isolation and again use the greedy algorithm to solve it.

That’s debilitating.  Partly solved problems become chronic.  There are only a few problems (matroid, if you care) where you get an optimal answer being greedy.  Worse yet, using the greedy algorithm denies you the ability to learn.  Because the breakdown appears later, you only learn to avoid that step and there may have been nothing wrong with it.  Nothing tells you to stop using the failure inducing first step.

A financial plan evolves over a long period.  You should not watch the next step too carefully because it can take you away from the overall strategy that you need.  Worse still, most of the good early steps are boring.

A mistake is your friend, but only if you learn something of value from it.  In this case Gordon Gecko was wrong.  Greed is not good.

Don Shaughnessy is a retired partner in an international accounting firm and is presently with The Protectors Group, a large personal insurance, employee benefits and investment agency in Peterborough Ontario.  don.s@protectorsgroup.com