Living with NP-Hardness: Approximation and Heuristics
Hardness rules out an exact fast method for every input, not a useful answer. An approximation algorithm carries a proved ratio to the optimum, while a heuristic carries no promise and has to be judged by measurement.
What a learner can do afterwards
- Run a 2-approximation for vertex cover and argue the factor from the matching it builds
- Distinguish an approximation with a proved ratio from a heuristic without one
- Choose between exact, approximate and heuristic for a stated deadline and input size
1 · Read
When a problem is NP-hard, no exact method runs fast on every input. That rules out perfection, not usefulness. You still have three doors: an exact method for small inputs, an approximation with a proved ratio, or a heuristic you judge by measurement. This lesson teaches you to pick the right door.
For vertex cover, build a matching: a set of edges that share no vertices. Take both ends of every matched edge into your cover. Every matched edge needs its own vertex in any optimum, so the optimum holds at least one vertex per matched edge. Your cover holds two per matched edge, so it is never larger than twice the optimum. That is a 2-approximation.
An approximation carries a promise that holds on every input, like never worse than twice the optimum. A heuristic carries no promise at all, so you judge it by testing on real inputs. Saying a heuristic usually works well reports measurements. It does not turn the heuristic into an approximation.
Match the method to the deadline and the input size. Small input with time to spare means exact. Huge input with a guarantee required means approximation. Huge input where good enough is fine, and you can test, means heuristic. Name what you are giving up before you start.
Hardness ends exact methods for every input, so promise a ratio with an approximation or measure a heuristic, and pick by deadline and size.
2 · Watch
Take it off screen
Where it sits
8 questions wait behind this lesson, each with its answer explained. Every answer feeds the sky: stars light as they are learned, and dim when it is time to come back.