Approximation algorithms find feasible answers to optimisation problems while proving how far those answers can be from the best possible answer. They are useful when exact optimisation is too expensive at the required scale, but an unexplained guess is not enough. The central question is precise: what quality can this method guarantee for every input covered by its assumptions?
The gold standard is a clear problem definition, a feasible output, a justified bound and an honest account of runtime and limitations. A method that performs well on yesterday’s examples has useful evidence behind it; a method with a proven approximation ratio also has a mathematical promise. Neither promise makes an inaccurate model trustworthy. This guide develops the distinction through small examples that you can reproduce with pencil and paper.
Start with the Gold Standard collection or the How X Works hub for the wider subject map. Combinatorial Optimization explains discrete decisions and exact solution methods. Algorithm Design supplies the broader background in correctness and complexity. Here we concentrate on the additional reasoning needed when an algorithm deliberately accepts a potentially suboptimal answer.
Choose your approximation algorithms route
Chapters 1–3: Define the guarantee
Chapters 4–6: Prove and calculate
Chapters 10–12: Check and transfer
Chapter index
Define the guarantee · Chapters 1–3
1. Decide exactly what is being approximated
Prove and calculate · Chapters 4–6
4. Work through a vertex-cover approximation
Compare methods · Chapters 7–9
7. Understand greedy set cover through marginal gain
8. Distinguish a universal theorem from an instance certificate
9. Choose between exact search, approximation and heuristics
Check and transfer · Chapters 10–12
10. Read schemes, runtime and randomness carefully
11. Diagnose misleading guarantees and implementation mistakes
Learn and practise · Chapters 13–14
CHAPTER 1 OF 14 · Define the guarantee
1. Decide exactly what is being approximated
An answer, an objective and a model
Imagine choosing inspection locations in a fictional network. Every connection must have an inspector at one of its endpoints. You want the smallest possible number of locations. There are three separate objects: a set of selected locations, the number of selected locations, and the network model describing which connections need inspection. An approximation algorithm may return a set whose size exceeds the minimum. It must still cover every required connection.
This matters because “almost right” has several incompatible meanings. Leaving one connection uncovered is a feasibility failure, not merely a slightly larger objective value. Choosing six locations when five suffice is a quality issue within the feasible region. Omitting a real connection from the input is a modelling failure even if the computed solution is optimal for the supplied graph. Keep these categories separate when discussing a result.
Write an output contract before choosing a method. State the decision variables, the hard constraints, the objective, the allowed input family and the required performance guarantee. For inspection locations, the contract might require an unweighted, undirected graph; a set of vertices covering all edges; and a number of selected vertices no greater than twice the optimum. This is a mathematical teaching model, not a recommendation for deploying physical inspectors.
Approximation is not numerical rounding
An approximate combinatorial solution can contain only exact integers. Selecting four vertices instead of an optimal three involves no rounding error in arithmetic. Conversely, an exact optimisation algorithm implemented with floating-point arithmetic can have numerical tolerances. These are different sources of error and require different checks.
The existing Mathematical Approximation guide covers the wider landscape of estimates, error bounds and numerical simplification. Use it when the question concerns a rounded measurement or a simplified function. Use the present guide when the question concerns a feasible decision whose objective value must be compared with an unknown optimum.
The first practical exercise is therefore linguistic. Replace “the result is approximately correct” with a statement identifying the object, the error measure and the conditions. If you cannot complete that sentence, you do not yet have a testable guarantee.
CHAPTER 2 OF 14 · Define the guarantee
2. Read approximation ratios without reversing them
Minimisation and maximisation
For a minimisation problem with nonnegative objective values, let OPT be the minimum feasible value and A the algorithm’s value. A factor-r guarantee, with r at least one, means A ≤ r × OPT. Feasibility already implies OPT ≤ A. Together these statements place the returned value between OPT and r times OPT. A factor of two does not say the algorithm always doubles the cost. It says the cost never exceeds that bound under the theorem’s assumptions.
For maximisation, we will use the convention A ≥ OPT/r, again with r at least one. Other texts state a fraction α between zero and one and write A ≥ α × OPT. Both conventions are useful, but a report must say which it uses. A “0.5 guarantee” for maximisation and a “2-approximation” can express the same relationship.
Consider a minimisation result costing 132 units. Suppose an independently justified lower bound is 120. Because 120 ≤ OPT ≤ 132, the result is at most 132/120 = 1.1 times optimal. We can certify a 10% multiplicative excess relative to the optimum without knowing its exact value. If the lower bound improves to 128, the certificate improves to 132/128 = 1.03125. The solution did not change; our knowledge of its quality improved.
Percentages need a denominator
The difference 132 − 120 is twelve units. Dividing twelve by 132 gives about 9.09%; dividing it by 120 gives 10%. Both computations are arithmetically correct, but they answer different questions. Solver gap conventions can use different denominators. Record the formula instead of copying a percentage with no definition.
Ratios also need care when the optimum is zero or objectives can be negative. If OPT = 0 in a nonnegative minimisation problem, a finite multiplicative guarantee forces A = 0. An additive error statement, A ≤ OPT + δ, can be more informative in other settings. Do not add a constant to every objective and assume the same ratio survives: addition changes ratios even when it leaves the identity of the best solution unchanged.
For example, costs two and four have ratio two. After adding 100 to both they become 102 and 104, whose ratio is about 1.0196. Nothing about the underlying choice improved. Only the numerical baseline changed.
CHAPTER 3 OF 14 · Define the guarantee
3. Build certificates before searching for clever methods
A lower bound is useful even when unattainable
A lower bound for a minimisation problem is a value that no feasible answer can beat. It need not itself describe a feasible answer. For scheduling jobs on identical machines, total work divided by the number of machines is a lower bound on completion time. A machine cannot process more than one unit of work per unit of time in this model. Some indivisible job lengths may prevent reaching the average exactly.
Suppose job lengths are eight, seven and six on two machines. Total work is 21, so the average bound is 10.5. The longest-job bound is eight. Combining them gives a lower bound of 10.5. Enumerating the possible partitions shows the optimum is thirteen: place seven and six together, and eight separately. The bound was valid but not tight. Validity and tightness are different properties.
A feasible schedule of thirteen and a bound of 10.5 give a certified ratio of 13/10.5, approximately 1.2381. Exhaustive enumeration strengthens the conclusion to exact optimality. If you stop before enumeration, report the weaker certificate honestly. A weak lower bound does not prove that the feasible schedule is poor.
Three reusable constructions
Relax constraints to obtain an easier problem whose optimum cannot be worse for minimisation. Identify unavoidable independent obligations, each of which requires some resource. Or sum a conserved quantity, such as total work, and divide by the total available capacity. These constructions appear in many different algorithms because they create something against which an unknown optimum can be compared.
Before trusting a certificate, explain why every feasible solution obeys it. “The average observed in our previous runs” is not automatically a lower bound. “Another heuristic returned this value” is ordinarily an upper bound for minimisation if that heuristic’s output is feasible. Reversing these directions can produce a convincing but false optimality claim.
Keep the certificate with the solution record. A selected set, its objective, a checked constraint report and a lower-bound witness are more useful than a score alone. They let another person reproduce the reasoning without trusting the algorithm’s reputation.
Select disjoint obligations
Take an undirected graph with vertices A, B, C, D and E. Its edges are AB, BC, CD and DE: a path of five vertices. A vertex cover selects vertices so every edge has at least one selected endpoint. The set {B,D} covers all four edges, so a cover of size two exists.
Now run this procedure: choose an edge, select both endpoints, remove every edge incident to either endpoint, and repeat while edges remain. If the first chosen edge is AB, we select A and B and remove AB and BC. Choosing CD next selects C and D and removes CD and DE. The returned cover is {A,B,C,D}, of size four.
Why is it a cover? When an edge disappears, one of its endpoints has been selected. When the procedure finishes, no edge remains. Why is its size controlled? The explicitly chosen edges AB and CD do not share endpoints. Any cover must select at least one endpoint from each of these two disjoint edges. Thus every cover has size at least two, while our procedure selected exactly four vertices.
The same reasoning works for any graph in this unweighted model. If the procedure chooses k disjoint edges, it selects 2k endpoints. Any cover needs at least k vertices. Therefore the returned size is at most twice OPT. The selected edges form a matching that supplies the lower-bound witness.
Maximal does not mean maximum
A maximal matching cannot be extended by adding another edge without sharing an endpoint. A maximum matching has the largest possible number of edges. This approximation needs a maximal matching, which the procedure constructs. It does not require solving the harder-looking task of finding the largest matching before producing the cover.
The path example reaches the ratio two exactly: four selected vertices versus an optimum of two. That is a counterexample to any claim that this particular algorithm always achieves a ratio below two. It is not a claim that every run is this bad. Choosing BC first and then DE still returns four, while different graphs can produce optimal covers.
The guarantee also does not transfer automatically to weighted vertices. If A costs 1,000 and B costs one on a single-edge graph, choosing both costs 1,001 while choosing B alone costs one. Counting endpoints no longer controls total cost. The changed objective invalidates the counting proof.
A fractional model of cover
For a weighted vertex cover, assign a nonnegative cost c(v) to each vertex. An integer decision x(v) is one when the vertex is selected and zero otherwise. For every edge uv, require x(u) + x(v) ≥ 1. Minimise the sum of c(v)x(v). Relax the decisions so they may take any value from zero to one. Every integer cover remains allowed, so the relaxed optimum is a lower bound on the integer optimum.
Given an optimal fractional solution, select every vertex with x(v) ≥ 1/2. Each edge has at least one endpoint meeting that threshold; otherwise its two endpoint values would sum to less than one. Hence the rounded set covers every edge. For each selected vertex, its full cost is at most twice its fractional contribution. Summing gives rounded cost at most twice the relaxed optimum and therefore at most twice the integer optimum.
The proof has two independent parts: feasibility after rounding, and cost after rounding. A rounding rule that controls cost but leaves an uncovered edge is not enough. Nor is a rule that always covers edges but selects arbitrarily expensive unnecessary vertices.
An original triangle check
Consider a triangle on A, B and C with every vertex cost equal to one. Setting all three fractional variables to one half satisfies every edge constraint and costs 1.5. Adding all three edge inequalities gives 2(x(A)+x(B)+x(C)) ≥ 3, proving that 1.5 is the fractional optimum.
Rounding at one half selects all three vertices and costs three. An integer cover needs two vertices and any pair works, so OPT = 2. The actual ratio is 3/2, although the general bound allows two. The fractional lower bound itself has a gap: integer optimum two divided by fractional optimum 1.5 is 4/3.
This example explains why a relaxation can be mathematically useful without representing an executable plan. Half a selected endpoint is a certificate-building device. Before implementation, discrete decisions must be recovered and checked. A numerical solver’s approximate fractional values also need tolerances and feasibility handling; do not turn a theoretical exact comparison into an unexamined floating-point test.
List scheduling
Assume m identical machines, positive job durations, no release times, no precedence constraints and no interruptions. Process jobs in a given order, assigning each to a currently least-loaded machine. This simple rule is called list scheduling. Its guarantee concerns makespan: the largest total load assigned to any machine.
Take two machines and jobs of lengths two, two and four, in that order. Assign the first two to machine 1 and the next two to machine 2. Both loads are now two. Put the final four on either machine. The final loads are six and two, so the makespan is six. The optimal arrangement is four alone and the two smaller jobs together, giving makespan four. The observed ratio is 1.5.
To understand the general bound, consider the job j that finishes last. Let its duration be p and its starting load be s. At the moment it was assigned, every machine had load at least s because we chose a least-loaded machine. If total work is W, the work already assigned is at least ms, and j contributes p. Therefore ms + p ≤ W, so s ≤ (W − p)/m.
The completion time is s + p ≤ W/m + (1 − 1/m)p. Every feasible schedule has makespan at least W/m and at least p. Substituting these two lower bounds gives completion time at most (2 − 1/m)OPT. For two machines, this is 1.5OPT, exactly the ratio reached by our example.
Check the model before using the theorem
If machines have different speeds, the least-loaded rule and its proof need reconsideration. If jobs cannot run on particular machines, an apparently idle machine might not be eligible. If job B must wait for A, total assigned load does not describe the full execution constraint. A theorem for independent jobs cannot be carried over by changing only the labels.
The exam-timetabling specialist article makes this distinction concrete. Examinations sharing candidates create conflicts, while rooms impose capacity and suitability constraints. Those requirements are not present in the identical-machine model above. Use the scheduling example to learn proof structure, then build the actual timetable model separately.
CHAPTER 7 OF 14 · Compare methods
7. Understand greedy set cover through marginal gain
Count newly covered requirements
Suppose a fictional testing plan must cover requirements {1,2,3,4,5,6}. Available test bundles are A={1,2,3,4}, B={1,2,5} and C={3,4,6}. Each bundle has equal cost. Greedy set cover repeatedly selects the bundle covering the largest number of requirements not already covered.
Initially A covers four requirements, more than B or C, so greedy selects A. The remaining requirements are five and six. B covers five and C covers six, so both are needed. Greedy uses three bundles. Yet B and C together cover all six requirements, so the optimum is two. The example demonstrates that the largest immediate gain need not lead to the smallest final selection.
After selecting a bundle, recompute gains against the uncovered requirements. Counting all elements in a set again would count already completed work as progress. If bundles have unequal positive costs, the natural weighted rule compares cost per newly covered requirement. That is a different selection calculation from choosing the largest set.
Why the loss can still be bounded
The classical greedy analysis gives a harmonic-number guarantee: for a universe of n elements, the unweighted method uses at most H(n) times the optimum, where H(n)=1+1/2+…+1/n and H(n) ≤ 1+ln n. This is a worst-case statement, not a prediction of the ratio on a particular instance. In our six-element example, the actual ratio is only 1.5.
The useful intuition is residual work. If an optimal solution uses k sets and r elements remain uncovered, those k sets collectively cover the remaining r elements. At least one therefore covers at least r/k of them. Greedy makes at least that much progress. As the remaining work shrinks, the number of steps can accumulate logarithmically rather than staying a fixed multiple independent of problem size.
Before running the method, check that every required element belongs to at least one available set. If element seven is required but appears in none of A, B or C, the instance is infeasible. The correct output is a clear failure report identifying that uncovered requirement, not an endless loop or a “nearly complete” cover presented as valid.
CHAPTER 8 OF 14 · Compare methods
8. Distinguish a universal theorem from an instance certificate
Two useful kinds of evidence
A universal approximation ratio describes a method across an entire class of inputs. An instance certificate describes the particular input and output in front of you. They answer different questions and can coexist. The matching-based cover method has a universal factor-two guarantee; on a specific graph, a stronger lower bound may prove that its returned cover is optimal.
Consider a triangle. The matching method selects the endpoints of one edge and removes all edges, returning two vertices. The matching contains only one edge, which gives a lower bound of one. But inspecting the triangle shows one vertex cannot cover the edge between the other two. This supplies a stronger lower bound of two. The returned solution is consequently optimal even though the matching witness alone did not establish that fact.
When reporting quality, use the strongest valid evidence you actually have. Do not report a worst-case bound as though it were a measured loss. Saying “the algorithm is within factor two” does not mean “we wasted half the resources.” Equally, an optimal answer on one triangle does not improve the universal guarantee for every graph.
A certificate ledger
For each run, retain the input version, the objective definition, the output, its checked value, the lower or upper bound as appropriate, and the reasoning supporting that bound. Include a solver status only with its meaning. “Feasible” establishes that an answer satisfies the encoded constraints; it does not by itself establish optimality.
If the best known feasible cost is 84 and the lower bound is 70, you can certify a factor of at most 1.2. If a later computation finds cost 77 with the same bound, the certificate becomes 1.1. If it instead strengthens the bound to 77 while leaving cost 84, the certificate becomes approximately 1.0909. Both types of progress matter.
This discipline is particularly valuable when an algorithm is interrupted. A partial search can still leave a useful feasible answer and a rigorous quality interval. Preserve both rather than reducing the entire computation to success or failure.
CHAPTER 9 OF 14 · Compare methods
9. Choose between exact search, approximation and heuristics
Difficulty does not dictate one response
An NP-hard optimisation problem is not a command to abandon exact methods. Small instances, restricted graph structures or favourable data can permit exact computation. Approximation algorithms are one response when a guaranteed compromise is valuable. Heuristics are another response when practical performance matters and a universal ratio is unavailable or too weak.
The appropriate choice depends on the cost of being suboptimal, the size and structure of the input, the time budget and the availability of certificates. A teaching exercise with five vertices should often be solved exactly to establish a reference answer. A much larger operational instance might benefit from a quick feasible solution followed by bounded search or improvement.
A heuristic is not automatically unreliable. It may be exceptionally effective on a well-understood distribution of inputs. The honest distinction concerns what has been established. Benchmark success is empirical evidence. A worst-case theorem is a mathematical statement under explicit assumptions. Neither should be relabelled as the other.
Combine methods without losing the guarantee
For minimisation, begin with a feasible solution from a factor-r approximation and then apply improvements that preserve feasibility and never increase the objective. The final result remains within factor r because it is no worse than the original guaranteed solution. This simple observation makes theoretical and practical methods compatible.
The preservation conditions matter. An improvement step that quietly relaxes a hard constraint can invalidate feasibility. A multiobjective preference change can invalidate the comparison. Retain the original feasible answer as a fallback and use an independent checker before accepting any replacement.
The cutting-stock specialist guide shows why this matters in material planning. Width loss, cutting rules and usable leftovers change the feasible patterns. A favourable bound for a simplified packing model is not automatically a guarantee for the factory’s actual cutting process.
CHAPTER 10 OF 14 · Check and transfer
10. Read schemes, runtime and randomness carefully
A smaller error parameter can cost much more
A polynomial-time approximation scheme, or PTAS, provides a family of algorithms with arbitrarily small prescribed multiplicative error, with polynomial runtime in input size for each fixed positive error parameter. A fully polynomial-time approximation scheme, or FPTAS, additionally has runtime polynomial in the reciprocal of that parameter. These definitions concern asymptotic dependence, not a promise of immediate practical speed.
Compare two hypothetical runtime formulas: n raised to the power 1/ε, and n cubed divided by ε squared. For fixed ε, both are polynomial in n. When ε shrinks from 0.1 to 0.01, the exponent in the first changes from ten to one hundred. The second multiplies its ε-dependent factor by one hundred. Constants and memory still matter, but the formulas explain why the distinction is substantial.
Do not promise an FPTAS merely because a program accepts a tolerance field. The required guarantee and runtime dependence must both be established. Some tolerances describe numerical feasibility, some describe an optimisation gap, and others are stopping heuristics. Their shared use of decimals does not make them interchangeable.
An expectation is not a per-run certificate
Randomised methods can have expected quality guarantees or high-probability guarantees. These are not the same as a deterministic bound that holds on every run. A report must identify what is random, what event is controlled and which probability statement has been proved.
For an elementary illustration, put each endpoint of every edge independently on one of two sides with equal probability. Any fixed edge crosses the partition with probability one half. By linearity of expectation, the expected number of crossing edges is half the total number of edges. This calculation does not require different edge-crossing events to be independent. It also does not say every sampled partition cuts half the edges: placing all vertices on one side cuts none.
Repeated trials and keeping the best can improve observed performance, but “we repeated it” is not a substitute for a probability analysis. Save random seeds when reproducibility matters and distinguish an expected guarantee from a verified bound on the returned instance.
CHAPTER 11 OF 14 · Check and transfer
11. Diagnose misleading guarantees and implementation mistakes
Failure patterns with different repairs
If the returned answer violates a hard constraint, repair feasibility first. A good objective value is irrelevant until the result belongs to the allowed set. If the answer is feasible but the claimed ratio looks impossible, inspect bound direction, objective units and the percentage denominator. If the theorem appears correct but performance collapses on new inputs, inspect whether the new inputs satisfy the theorem’s assumptions.
Common implementation errors include treating a maximal matching as though it must be maximum, using total set size instead of newly covered elements, failing to remove incident edges, and assigning a job to a machine that is not currently least loaded. Each error breaks a specific step in the proof. Use the proof as a debugging map rather than treating it as material separate from the program.
Ties also deserve an explicit rule. Different tie choices can return different feasible solutions while preserving the same worst-case guarantee. For reproducible examples, choose a fixed vertex order or machine identifier. For experiments, report the tie rule so that another reader can reproduce the run exactly.
Test the checker independently
For vertex cover, the checker should examine every original edge and confirm that at least one endpoint appears in the returned set. It should calculate cost from the original cost data. It should not trust the algorithm’s already-filtered list of remaining edges, since a bug in deletion could hide an uncovered edge from both algorithm and checker.
For scheduling, verify that every original job appears exactly once, sum durations for each machine and recompute the maximum load. A duplicated short job and an omitted long job can create an attractive but meaningless score. For set cover, rebuild the union of chosen sets and compare it with the original universe.
On tiny inputs, enumerate every feasible answer and compare against the exact optimum. This will not prove the algorithm for all inputs, but it can expose implementation errors and incorrect examples. Keep theorem checking, code testing and data validation as complementary activities with different jobs.
CHAPTER 12 OF 14 · Check and transfer
12. Transfer the reasoning when the problem changes
Changed-context exercise
Return to the five-vertex path A–B–C–D–E. In the unweighted problem, {B,D} is optimal with size two, while our matching procedure returned four vertices. Now assign costs A=1, B=100, C=1, D=100 and E=1. What changes? Is the old optimal set still best? Does the old factor-two counting proof certify the new cost?
The set {A,C,E} covers every edge and costs three. The old set {B,D} costs 200. Any cover omitting both expensive vertices must select A, C and E; that gives cost three. Any cover using an expensive vertex already costs at least 100. Hence the weighted optimum is three. Our previous matching choices select A, B, C and D, costing 202. The ratio is 202/3, approximately 67.33.
The algorithm still returns a feasible cover, but its old cost guarantee is gone. The failed proof step is exactly the substitution of “number of selected vertices” for “sum of selected costs.” The weighted fractional-rounding method addresses a different objective and retains its own guarantee under nonnegative costs.
Change a scheduling assumption
Return to jobs two, two and four on two machines. Suppose the four-unit job is now required to run after both shorter jobs finish. The old optimal partition alone no longer describes a valid concurrent execution. The two short jobs can run together from time zero to two, followed by the long job from two to six, so makespan six is attainable. A precedence chain through one short job and the long job already requires six units, proving optimality.
This changed problem has a different lower-bound witness. Total work divided by two still gives four, but the precedence constraint strengthens the lower bound to six. The lesson is not that the original method was wrong. The model changed, so the proof obligations changed too.
The Education guide treats this ability to rebuild an explanation under changed conditions as a practical test of learning. Explain the broken assumption before proposing a replacement algorithm.
CHAPTER 13 OF 14 · Learn and practise
13. Questions readers should ask before trusting a result
Does a factor-two guarantee mean twice the optimum?
No. It is an upper limit for a minimisation result, not an equality or an average. The method may return an optimal solution on many inputs. To assess the particular result, seek a stronger instance bound or an exact comparison on manageable data.
Can I compare ratios from different objectives?
Not directly. A guarantee about the number of selected locations does not guarantee their total cost. A guarantee about maximum machine load does not guarantee average waiting time. A change of units by a positive multiplicative factor preserves a ratio, but adding a baseline or changing objective components can alter its meaning.
Is an approximation algorithm always faster than exact optimisation?
No. Theoretical runtime classes and practical runtime are different. A sophisticated approximation can have large constants, while an exact solver may solve a particular small or structured instance quickly. Compare methods on representative inputs and retain their distinct guarantee statements.
Can a local optimum be called near-optimal?
Only with additional justification. A local optimum means no permitted local move improves the objective. Whether that implies a useful global ratio depends on the problem, the move set and a proof. Changing the neighbourhood can change both computational cost and what local optimality says.
What if the lower bound exceeds the feasible cost?
For a correctly defined minimisation problem, a valid lower bound cannot exceed a feasible objective value. A contradiction points to mismatched input versions, different objectives, numerical tolerance issues, an invalid bound or an infeasible purported solution. Stop and reconcile those records before publishing a gap.
What is the minimum honest result report?
Identify the input and constraints, show a feasible answer and its checked objective, state the bound and its derivation, define the approximation convention, and disclose relevant runtime and modelling assumptions. If no rigorous quality bound is available, say that the quality assessment is empirical. That is more useful than attaching an unsupported guarantee to a plausible result.
Week one: contracts and exact reference answers
Choose small graphs with at most six vertices. Draw their edges and enumerate all vertex subsets to find the exact minimum cover. Include a path, a triangle, a star, disconnected edges and a graph with no edges. Write the output contract and an independent cover checker before implementing any approximation. Explain why the empty graph has optimum zero and why ratio division needs special handling there.
Week two: algorithms and witnesses
Implement the matching-based cover procedure and list scheduling. Save the chosen matching or the job-assignment trace, not just the final score. Reproduce the four-vertex cover on the five-vertex path and the six-unit schedule for jobs two, two and four. Then alter input order and tie rules while keeping the models fixed. Record which results change and which guarantees remain valid.
Week three: bounds and adversarial cases
Add weighted costs and set-cover examples. Reproduce the 202-versus-three weighted counterexample and explain why it defeats the unweighted argument. For each small input, calculate the exact optimum and compare it with the available bound. Look deliberately for cases where a bound is weak, a greedy choice is misleading or an attractive solution is infeasible. This is a more demanding exercise than collecting only successful demonstrations.
Week four: a realistic model and a cautious conclusion
Select a modest real planning question, such as choosing a set of software checks to cover explicitly listed requirements. Describe where the set-cover model fits and where it does not. A test may only partly assess a requirement; tests may interact; costs may vary. Decide which effects must become hard constraints and which are outside the current exercise. Do not claim a theoretical guarantee for facts that the model does not encode.
Finish with a short reproducible report containing the input, output, independent feasibility check, objective, certificate and changed-context test. A second person should be able to rerun the small examples and identify the assumptions without asking you to reconstruct them from memory. That is a useful standard of competence in approximation algorithms: a result whose quality can be explained and whose limitations can be located.
Sources and further study
For standard algorithm statements and further proofs, consult Carnegie Mellon’s approximation-algorithms lecture, MIT’s set-cover lecture and Stanford’s approximation-algorithms course map. The numerical instances and changed-context exercises above are constructed teaching examples, not operational performance claims. Continue with the linked algorithm-design and combinatorial-optimisation roots when you need fuller background in exact methods, modelling and complexity.