Wait, What?
Sometimes the professional goal is not to find the perfect answer. It is to prove how far from perfect your fast answer can be.
Many important optimisation problems become computationally difficult as instances grow. Approximation algorithms respond with a disciplined compromise: produce a solution efficiently and prove a bound relating its quality to the optimum. The word approximation therefore does not mean “rough guess.” It means a mathematically controlled trade-off.
Quick Answer
Learn approximation algorithms through the sequence exact problem → hardness motivation → feasible solution → lower or upper bound on OPT → approximation ratio → proof → counterexample → technique transfer. Begin with simple examples such as vertex cover, then progress to greedy covering, local search, linear-programming relaxation, rounding and approximation schemes.
1. First Separate Three Different Questions
- Can we find an exact optimum?
- Can we find a good feasible solution quickly?
- Can we prove how good that solution is compared with optimum?
These are not the same problem. A heuristic may produce excellent answers in practice without a worst-case quality guarantee. An approximation algorithm adds a theorem about solution quality under a stated model.
2. Understand What an Approximation Ratio Means
For a minimisation problem, a common guarantee says that the algorithm’s cost is at most a factor of the optimal cost. For a maximisation problem, conventions are written differently so that the ratio still communicates closeness to optimum. The learner should not memorise symbols before understanding the comparison: algorithm result versus an expensive or unavailable exact benchmark.
The most important habit is to write which direction is better. In minimisation, smaller is better. In maximisation, larger is better. This prevents ratio formulas from becoming detached from meaning.
3. Learn the Proof Pattern Before the Technique Catalogue
Many approximation proofs can be studied using a common skeleton.
- Construct a feasible solution.
- Identify a quantity that every optimal solution must pay, contain or satisfy.
- Relate the algorithm’s cost or value to that bound.
- Conclude the approximation factor.
- Search for an instance that comes close to making the bound tight.
This turns approximation from a catalogue of tricks into a recurring proof relationship.
4. A Beginner Worked Idea: Vertex Cover
In a graph, a vertex cover chooses vertices so every edge has at least one endpoint selected. A classic approximation chooses the two endpoints of edges in a maximal matching. The learning value is the certificate behind the factor: because matching edges share no endpoints, every valid vertex cover must choose at least one endpoint for every matched edge, while the approximation chooses two.
That lower-bound relationship is what turns a feasible construction into a provable approximation. See MIT OpenCourseWare on approximation algorithms and Johns Hopkins approximation algorithms course materials.
5. The Major Design Families
Greedy construction. Make a locally attractive choice, then prove that repeated choices accumulate a bounded loss. Set cover is a central example where the interesting work lies in the analysis, not merely the greedy rule.
Local search. Start from a feasible solution and repeatedly improve nearby structure. The proof asks what a locally optimal solution must imply about a globally optimal one.
Relaxation and rounding. Replace a hard discrete constraint with an easier continuous problem, solve the relaxed problem, then map the fractional solution back to a valid discrete solution while controlling the loss.
Approximation schemes. A PTAS allows the user to request solutions arbitrarily close to optimum, with polynomial running time for each fixed accuracy setting. An FPTAS imposes a stronger efficiency requirement in how running time depends on both input size and accuracy. The learner should ask what computational price is paid for better accuracy.
Stanford’s approximation algorithms course describes the field as efficient algorithms for NP-hard optimisation problems that return provably near-optimal solutions, covering greedy methods, local search, relaxations and rounding. See Stanford MS&E 319.
6. Approximation Is Not the Same as Randomisation
A randomized algorithm uses random choices. An approximation algorithm gives a quality guarantee relative to optimum. An algorithm can be randomized without approximating an optimisation problem, approximate without using randomness, or do both. Keep these dimensions separate. The existing Randomized Algorithms draft owns random-choice guarantees; this page owns near-optimality guarantees.
7. Approximation Is Not the Same as “Works Well Usually”
A heuristic can be useful without a formal worst-case guarantee. Approximation analysis asks for a bound that survives every instance covered by the theorem. Empirical performance still matters in engineering, but it answers a different question. A strong learner should be able to say whether a claim is theoretical, empirical or both.
8. Common Learning Failure States
- Memorising approximation factors without reconstructing the bound.
- Calling every non-exact method an approximation algorithm.
- Assuming NP-hard means “cannot be solved” rather than distinguishing instance size, exact exponential methods, parameterisation and approximation.
- Forgetting whether the problem is minimisation or maximisation.
- Using the optimal value inside an algorithm that is supposed to avoid computing it.
- Proving feasibility but not quality.
- Proving a ratio for one problem variant and silently applying it to another.
9. The Scaffold-Fade Learning Ladder
- Level 1: calculate the quality ratio for supplied algorithm and optimum values.
- Level 2: follow a complete approximation proof and label construction, bound and comparison.
- Level 3: complete a missing inequality or lower-bound argument.
- Level 4: find an example where a tempting heuristic has poor quality.
- Level 5: derive a guarantee for a simple algorithm.
- Level 6: choose between greedy, local-search or relaxation-based approaches.
- Level 7: analyse how the guarantee changes when the problem contract changes.
Computing-education evidence supports making structural subgoals explicit for novices and fading support as they gain control. Subgoal-labelled worked examples can improve formative programming performance, while transfer still needs to be tested rather than assumed. See Margulieux, Morrison and Decker (2020).
10. Counterexamples Are Part of Mastery
For every new approximation strategy, ask the learner to construct an input where the algorithm is visibly not optimal. Then ask how bad that gap can become. This prevents “near-optimal” from becoming an intuition without a bound.
11. Immediate, Delayed and Transfer Checks
- Immediate: explain the guarantee in plain language.
- Delayed: reconstruct the proof skeleton without notes.
- Counterexample: produce an instance where the approximation differs from optimum.
- Transfer: identify what kind of bound might support a new optimisation problem.
- Professional: separate theoretical guarantee from measured performance on a workload.
12. AI Assistance Boundary
Use AI as a critic after an attempt: ask for a counterexample to a proposed ratio, ask which inequality is unjustified, or ask whether a claimed lower bound really applies to every feasible optimum. Do not outsource the key act of connecting the algorithm’s constructed solution to the bound on OPT.
Professional Direction
Advanced study extends into linear and semidefinite programming, primal-dual methods, randomized rounding, metric embeddings, hardness of approximation and problem-specific approximation schemes. Cornell, Stanford, MIT and other advanced algorithms courses place these techniques alongside graph optimisation, probability and complexity because approximation lives at the intersection of design, proof and computational limits.
Algorithm-learning rule: an approximation algorithm earns trust not because its answer looks close to optimal, but because the learner can explain the feasible construction, the benchmark on optimum and the proof that connects them.
eduKate Sengkang 