Good enough by dinnertime
Planning the absolute shortest road trip through 50 cities could take a computer years, but a clever shortcut finds a nearly-shortest route in seconds. When a problem is too hard to solve exactly, we cope with heuristics that are fast and good enough.
When exact is too slow
For NP-hard problems we rarely expect fast exact answers, so we relax something. An approximation algorithm runs quickly and provably comes within a guaranteed factor of optimal. A heuristic gives good answers in practice without a guarantee.
Traveling Salesman: exact is exponential; a 2-approximation returns a tour ≤ 2× the shortest.
Lab · Guarantee or not?
- One method promises 'within 1.5× of optimal, always'.
- Another 'usually works well but no promise'.
- Label each approximation vs. heuristic.
What you should see: A proven factor bound makes it an approximation algorithm; 'usually good, no bound' is a heuristic.