A probe-selection tool claims a proven 2-approximation for total probe cost — what exactly does that ratio promise about any single run?
answer
- a promise about quality, not speed
- measured against the best possible answer
- holds on every input, worst case
- direction flips for maximisation
- proved against a surrogate lower bound
basics
~20 sA 2-approximation promises that on every input the returned cost is at most twice the best possible cost. It is a proven worst-case ceiling on answer quality, not an average over inputs and not a statement about running time.
solid answer
~40 sThe ratio compares output quality against the optimum, never against a runtime budget. For a minimisation objective, a `rho`-approximation returns a feasible solution with `cost(ALG) <= rho * OPT` on **every** instance it accepts, so `rho = 2` means the probe set it picks is never more than twice the price of the cheapest covering set — and on most real inputs it lands far closer. The bound is proven without computing `OPT`: the argument compares the output against a quantity that provably cannot exceed the optimum, which is why the algorithm stays polynomial. Two things the number does not say: nothing about the typical gap, and nothing about how long a run takes. For a maximisation objective the inequality flips, so always state the direction you mean.
go deeper
Remember the shape: an approximation ratio compares the answer's quality to the best possible answer, and it is a promise that holds on every input. It has nothing to do with how fast the algorithm runs.
Be able to write cost(ALG) <= rho * OPT for minimisation, flip it correctly for maximisation, and explain that the bound is proven against a surrogate lower bound rather than measured against a computed optimum.
Show you know what the guarantee does not cover: the typical gap, the runtime, composition across pipeline stages. If a per-run number is wanted, say you would compute a lower bound for that instance and report the observed ratio against it.
The judgment is what to put in writing. A constant factor is contract-grade because it is scale-free and adversary-proof; empirical closeness is evidence about one input distribution. Decide which of those the commitment actually needs before picking the algorithm.
## What the ratio compares An approximation guarantee is a statement about **answer quality**, and it always names three things: the objective being measured, the direction of the inequality, and what sits on the other side of it. For a minimisation problem — "pick the cheapest set of probes that still covers every service" — a **`rho`-approximation** is a polynomial-time algorithm that, on every input it accepts, returns a *feasible* solution whose cost satisfies `cost(ALG) <= rho * OPT` where `OPT` is the cost of the best feasible solution **for that same input**. With `rho = 2` the promise reads "never more than twice the cheapest possible". Three words carry all the weight: - **never** — it is a worst-case bound over all admissible inputs, not a tendency, not an average, and not a claim about the inputs you happen to have; - **feasible** — every service is still covered; an approximation weakens *optimality*, never the constraints; - **that same input** — the comparison is per instance, so there is no averaging across a workload and no distribution assumed. ## Direction, because the inequality flips "A factor of two" is ambiguous until you say which way the objective points. Both conventions are in use, and mixing them produces a guarantee that is either vacuous or backwards. | Objective | Usual written form | Reading | |---|---|---| | Minimisation (cost, probes, cover size) | `ALG <= rho * OPT`, with `rho >= 1` | 2 means "never worse than twice the cheapest" | | Maximisation (coverage, satisfied clauses, value) | `ALG >= OPT / rho`, with `rho >= 1` | 2 means "never less than half the best" | | Maximisation, fraction form | `ALG >= alpha * OPT`, with `alpha <= 1` | 7/8 means "never less than seven eighths of the best" | A good habit is to state the ratio with its objective attached — "a 2-approximation for minimum cover cost" — so the direction travels with the number. ## The optimum is never computed The question candidates stumble on is: if finding `OPT` is intractable, how can a fast algorithm know it is within a factor of it? It does not know it per run. The **proof** does the work, and it does it by comparing the output against a *surrogate* — some quantity that is computable and is provably no larger than the optimum for a minimisation problem (the size of a maximal matching, the weight of a minimum spanning tree, the value of a relaxation). If the output is at most `rho` times the surrogate, and the surrogate is at most `OPT`, the guarantee follows for every instance. Designing and proving such an argument belongs to algorithm design; what matters for reading a guarantee is the shape of it: the certificate of quality is mathematical and established once, not measured per run. A practical consequence falls straight out of that: the output alone tells you nothing about how close you actually are. If you want a per-run number, you must also compute a lower bound on the optimum for that instance and divide. ## The factors worth recognising A handful of ratios recur so often that interviewers treat them as vocabulary. | Problem | Guarantee usually quoted | Shape of the factor | |---|---|---| | Minimum vertex cover | 2 | a small constant, and no better than roughly 1.36 is achievable unless P = NP | | Minimum set cover | about the natural logarithm of the number of elements | grows with the input; essentially best possible unless P = NP | | Tours with costs obeying the triangle inequality | 3/2, and 2 by a simpler argument | a constant, independent of input size | | Tours with arbitrary costs | none | no polynomial-time factor at all unless P = NP | Note the difference in kind between rows two and one: a **constant** factor is a promise you can put in a contract regardless of scale, while a factor that grows with the input means the promise degrades as the estimate grows. ## What the number does not promise 1. **Nothing about running time.** "2-approximation" is not "twice as slow"; the time bound is a separate claim, stated separately. 2. **Nothing about typical behaviour.** Instances that actually achieve the worst case are often contrived. Measuring 1.05 on production data neither confirms nor contradicts a factor of 2. 3. **Nothing about the end-to-end pipeline.** Two stages, each within a factor of two of their own objectives, do not compose into a 4-approximation of some third objective; each guarantee is about the objective it was proved for. 4. **Nothing about stability.** The returned solution can change completely when a single input changes, while still respecting the bound. The single reliable reading: a ratio is a **worst-case, per-instance, quality-only ceiling, proven in advance**. Everything else about the algorithm has to be claimed on its own evidence.
- Your run of the 2-approximation comes out 1.1 times the cost you believe is optimal. Does that undermine the guarantee?No. The factor is a worst-case ceiling, so anything at or below it is consistent, and most instances sit well under. Be careful about the denominator too: unless you solved the instance exactly, "the cost you believe is optimal" is usually a computed lower bound, which makes the measured 1.1 itself an upper estimate of the true ratio.
- How is the same guarantee stated when the objective is to maximise coverage rather than minimise cost?The inequality flips. You either write `ALG >= OPT / rho` with `rho >= 1`, so a 2-approximation returns at least half the best achievable coverage, or you write the factor as a fraction at most one, as in a 7/8-approximation. Both are common, which is why the direction must be said out loud rather than inferred from the number.
- Does a 2-approximation ever return the optimal solution?Often, yes — the ratio bounds the worst case, not every case, and on many structured inputs the algorithm is exactly optimal. What it cannot do is *tell you* that it was optimal. Recognising optimality would generally require solving the problem, which is the cost the approximation was chosen to avoid.
It is a shipping guarantee, not a timetable: the carrier commits that no parcel ever costs more than twice the cheapest rate, which says nothing about how fast it moves or what you typically pay.
- Reads the factor two as a running-time claim rather than a quality claim.
- Treats the ratio as an average over inputs instead of a worst-case bound.
- Believes the algorithm must compute the optimum to know it is within two.
- Expects the output to land near exactly twice the optimum on typical inputs.
- Applies the minimisation form of the inequality to a maximisation objective unchanged.
- Says a low measured ratio on production data disproves or strengthens the proven bound.