Living with NP-Hardness: Approximation and Heuristics
A polynomial-time exact solver for an NP-hard optimization problem would imply P=NP, which remains unresolved. Approximation algorithms provide proved quality bounds within their stated domain. Heuristics without such bounds are evaluated through measurements of quality and cost.
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
Earlier you saw exact dynamic-programming methods. NP-hardness does not prove that every instance takes a long time. A polynomial-time exact solver for an NP-hard optimization problem would imply P=NP; whether P=NP remains unresolved. Under the usual assumption P differs from NP, no such solver handles all inputs. Exact methods can still be useful on small or structured instances.
Use an unweighted undirected graph with no self-loops. A vertex cover selects vertices so every edge has a selected endpoint. A matching has edges with no shared endpoints. Build a maximal matching: pick an edge, remove every edge touching either endpoint, and repeat until none remain. Select both endpoints of each picked edge. Maximal means no further edge can be added; maximum means largest possible.
Maximality makes the selected endpoints a cover: any uncovered edge could be added to the matching, contradicting maximality. If m edges were picked, the cover has 2m vertices. Every cover needs a different vertex for each picked edge because those edges share no endpoints. Thus the optimum OPT is at least m, and 2m is at most 2OPT.
Consider edges AB, BC and CD, where each letter names a vertex. Picking BC removes all three edges. The matching is maximal, and its endpoints B and C cover every edge. It is not maximum: AB and CD form a larger matching. A maximum matching is unnecessary for the factor-2 proof.
For a minimization problem, a ratio-r approximation returns a feasible answer of cost at most r times the optimum on every input in its stated domain, with polynomial running time. Here r is at least 1. A factor 2 is an upper bound, not a requirement to be exactly twice optimal. A heuristic may guarantee feasibility or runtime without providing a proved bound on solution quality.
Evaluate a heuristic on representative inputs. Record runtime, memory and solution quality. Where an optimum is known, compare against it; otherwise a proved bound can help assess the gap. Tests show performance on tested cases. Unless they exhaust a finite stated domain, they do not prove an approximation ratio for all inputs.
Choose from methods actually available for the problem. An exact solver is suitable if it meets the deadline and stays within the available resources. An approximation must meet any required ratio and also finish in time. A tested heuristic may be suitable when no proved quality ratio is required. Large input size alone rules out none of these choices; check the problem, assumptions and measured costs.
Qualify hardness claims. Prove both feasibility and the approximation bound. Choose an available method whose guarantees and costs meet the task.
Original lesson, questions, worked solutions and flashcards written for this dataset.
Three original readings written for this dataset about vertex-cover guarantees, comparing solvers, and computational limits.
More to read
Check feasibility before the ratio
A minimization algorithm must first return an answer that obeys the constraints. For vertex cover, this means every edge touches a selected vertex. A small collection of vertices is not useful if an edge remains uncovered.
Consider an unweighted undirected graph without self-loops. Repeatedly choose an edge and remove all edges touching either endpoint. Continue until no edges remain. The chosen edges form a matching because their endpoints are disjoint. It is maximal because no further disjoint edge can be added.
Select both endpoints of each chosen edge. Every removed edge touches a selected endpoint, so this selection covers the graph. If the matching has m edges, the selection contains 2m vertices.
Now compare with an optimal cover. Each of the m disjoint edges needs an endpoint in any cover. No vertex can serve two of those edges, so every cover has at least m vertices. The algorithm's 2m vertices are therefore at most twice the optimum.
The proof has two jobs: establish a valid cover, then bound its size. An arbitrary nonmaximal matching supplies the lower bound but may leave edges uncovered. A maximum matching is unnecessary; maximality is enough.
Compare solvers on the task you have
Write the requirements before timing a solver. State the deadline, memory limit and any required solution-quality guarantee. Also check whether the algorithm applies to the input: a proof for one problem variant may not apply to another.
For a fair implementation comparison, use the same input cases and record the computing conditions. Measure runtime and memory, and verify that returned answers obey the constraints. Repeat trials when timings vary.
Measure quality separately from speed. Small cases may allow an exact solver to find the optimum. For a minimization problem with positive optimum cost, divide the returned cost by the optimum to obtain an observed ratio for that case. When the optimum is unknown, a proved lower bound can help evaluate the result, but report it as a bound.
Try different input sizes and structures. A sample can reveal poor results or slow cases. It cannot establish a guarantee for all inputs outside that sample.
Use measurements together with proofs. An exact method may meet the deadline on your instances. An approximation may provide the required ratio yet need too much memory. A heuristic without a quality bound may still be useful when measured performance meets the task's requirements. Record what is known and what remains uncertain.
A slow search is not an undecidable problem
A finite 0/1 knapsack instance has finitely many subsets. Enumerating them and comparing feasible values gives an exact answer. The search may be too expensive, but an exact algorithm exists. The capacity table is another exact method, with work depending on numeric capacity.
NP-hardness does not mean that exact algorithms are impossible. A polynomial-time exact solver for an NP-hard optimization problem would imply P=NP. Whether P=NP remains unresolved. The usual claim that no such solver exists assumes P differs from NP.
Undecidability concerns a different requirement. A decision algorithm must terminate and give the correct yes-or-no answer on every valid input. For an undecidable problem, no algorithm meets that requirement.
The general halting problem asks whether a supplied program eventually stops on a supplied input. There is no algorithm that decides this correctly for every program-input pair. That does not prevent deciding particular easy cases.
A timeout does not decide nontermination. A program that has not stopped after a minute might stop later. The timeout reports an observation, not a proof that it runs forever.
When choosing a solver, distinguish an expensive exact computation from a problem with no general decision algorithm. Approximation guarantees and measured heuristics address particular goals; neither is a general cure for undecidability.
2 · Watch
En anglaisTake it off screen
Where it sits
Learn first
Optional connections
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.