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.
saying these in an interview costs you the question
- 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.