--- title: "Living with NP-Hardness: Approximation and Heuristics" description: "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. Heuris" canonical: https://lightmysky.com/learn/computing/living-with-np-hardness-approximation-and-heuristics-mt_tZ82ty6h2u source: https://lightmysky.com/learn/computing/living-with-np-hardness-approximation-and-heuristics-mt_tZ82ty6h2u.md retrieved: 2026-11-12 --- > **Agent view.** This is the Markdown twin of the page, for tools and assistants. > When to use this site, and the call that answers each job: https://lightmysky.com/agent-instructions.md > API description (OpenAPI 3.1): https://lightmysky.com/openapi.json · Authentication: https://lightmysky.com/auth.md > Pricing: https://lightmysky.com/pricing.md · Catalog: https://lightmysky.com/llms.txt · Full catalog: https://lightmysky.com/llms-full.txt > Every machine-readable file on this domain: https://lightmysky.com/.well-known/ai-catalog.json > Ask for Markdown with `Accept: text/markdown`, a `.md` address, or `?mode=agent`. # 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. Subject: Computing · Area: Algorithms & Data Structures · Ages 21 to 22 Page: https://lightmysky.com/learn/computing/living-with-np-hardness-approximation-and-heuristics-mt_tZ82ty6h2u ## Ready when they can - 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 ## Lesson: Good answers without perfect ones 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. *(drawing: The matching gives a lower bound on any cover. Taking both endpoints gives twice that bound.)* **Example.** 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. **Recap.** 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.* ## Practice 8 questions on this page, each with its working shown. ## Needs first - [P, NP and What NP-Complete Means](https://lightmysky.com/learn/computing/p-np-and-what-np-complete-means-mt_wwmNVG_VnB) ## Optional connections - [Greedy Choice and the Exchange Argument](https://lightmysky.com/learn/computing/greedy-choice-and-the-exchange-argument-mt_9Fj28VDAV-) ## Opens up - [Randomised Algorithms and the Probabilistic Method](https://lightmysky.com/learn/computing/randomised-algorithms-and-the-probabilistic-method-mt_4ShN_WlT0-) - [Approximation Ratios and How One Is Proved](https://lightmysky.com/learn/computing/approximation-ratios-and-how-one-is-proved-mt_8pmBztDkFD)