What is an approximation algorithm

Setting perfection aside for a moment

Here's a hard problem. To find the perfect answer, you'd have to check every case, and there are an enormous number of them.
Go all the way, and you'll certainly get the best answer. But when will that be?
Press and count for yourself.

What happens if you check everything for the perfect answer. (the cases multiply and the time explodes → no end in sight)

The numbers grow far too fast. Add just a few items, and there's several times as much to check.
So waiting all the way for the perfect answer isn't always realistic. But that doesn't mean we can just give up.

A good enough answer, fast

Here's an idea. What if it doesn't have to be the very best?
Instead of aiming for perfection, you just quickly pull out a "reasonably good answer," snapping up the good options in front of you the way greedy did.

A quick rough answer vs the perfect answer. (the rough answer comes in an instant · the gap is small)

The rough answer appeared in the blink of an eye, and it's barely different from the perfect one.
It falls a little short, but it's usable. In many cases, this is good enough.

Guaranteeing how good it is

There's one worry, though. Can we trust a "reasonably good answer"? What if it's a terrible one?
That's why clever methods come with a promise: "this answer won't be much worse than the best."

Guaranteed within 1.5 times the optimum. (whatever answer comes out stays inside this line → the worst case is capped)

This is the really wonderful part. Draw a line like "within 1.5 times the optimum," and however bad the answer gets, it can't cross that line.
It isn't perfect, but we know exactly how far short it can fall. That's completely different from a vague guess.

Trading accuracy for time

In the end, it's a balance scale. Spend more time and the answer gets more accurate; save time and the answer gets a little rougher.
You can't say once and for all which side is better: the fast side if you're in a hurry, the accurate side if you need precision.
Use the buttons to add or save time and choose a point between the two.

Spend more time for more accuracy, less for less. (where to stop is our choice)

This scale is the heart running through all of algorithms: the fast way and the accurate way, the simple way and the thorough way.
Each time, we've chosen what to give up and what to gain. Knowing good methods means reading this scale well.

How far we've come

We've come a long way. Starting from solving things in order, we lined things up, searched, measured costs, split, connected, and chose.
We've also seen that some problems are truly hard, and that there are still good enough answers for them.
Press to look back over the whole road at once.

Four things this area has given us, in order. (good methods · speed · strategy · knowing the limits and compromising)

Not every problem can be solved perfectly. But that doesn't mean we're powerless.
With fast methods and clever strategies, and by knowing the limits and compromising wisely, you can get a usable answer even in the face of hard problems.
That's the power algorithms give us.