The Algorithm Design Manual Second Edition

9.10

Dealing with NP-complete Problems

For the practical person, demonstrating that a problem is NP-complete is never

the end of the line. Presumably, there was a reason why you wanted to solve it

in the first place. That application will not go away when told that there is no

polynomial-time algorithm. You still seek a program that solves the problem of

interest. All you know is that you won’t find one that quickly solves the problem

to optimality in the worst case. You still have three options:

• Algorithms fast in the average case – Examples of such algorithms include

backtracking algorithms with substantial pruning.

• Heuristics – Heuristic methods like simulated annealing or greedy approaches

can be used to quickly find a solution with no guarantee that it will be the

best one.

Approximation algorithms return solutions with a guarantee attached, namely

that the optimal solution can never be much better than this given solution. Thus

you can never go too far wrong when using an approximation algorithm. No matter

what your input instance is and how lucky you are, you are doomed to do all right.

conceptually simple, very fast, and easy to program.

One thing that is usually not clear, however, is how well the solution from an

approximation algorithm compares to what you might get from a heuristic that

gives you no guarantees. The answer could be worse or it could be better. Leaving

your money in a bank savings account guarantees you 3% interest without risk.

Still, you likely will do much better investing your money in stocks than leaving it

in the bank, even though performance is not guaranteed.

One way to get the best of approximation algorithms and heuristics is to run

both of them on the given problem instance and pick the solution giving the better

result. This way, you get a solution that comes with a guarantee and a second

chance to do even better. When it comes to heuristics for hard problems, sometimes

you can have it both ways.

• Approximation algorithms – The theory of NP-completeness only stipulates

that it is hard to get the exact answer. With clever, problem-specific heuris-

tics, we can probably get close to the optimal answer on all possible instances.

Furthermore, approximation algorithms realizing provably good bounds are often

---

9 . 1 0

D E A L I N G W I T H N P - C O M P L E T E P R O B L E M S