Choosing between a proven 2-approximation and an in-house heuristic that landed within three percent on last quarter's probe data, what belongs in a written cost commitment?
answer
- promise versus expectation
- one distribution or every input
- take the better of both answers
- a lower bound certifies each run
- relaxation value bounds the optimum below
basics
~20 sOnly the proven factor belongs in the commitment, because it holds on inputs nobody has seen yet; measured closeness describes one past distribution. The strong plan runs both, returns the cheaper answer, and certifies each run against a computable lower bound.
solid answer
~50 sA proven ratio and an observed ratio are different kinds of evidence. The factor of two is a **worst-case, per-instance** statement that survives an adversarial or simply changed input; the three percent is a **measurement on one distribution** that carries no promise once the fleet shape, pricing or scale moves. So the written ceiling should be the proven one. That does not mean discarding the heuristic: run both and return the cheaper result, and the combined output still satisfies the factor of two while usually matching the heuristic. Then add per-run certification — compute a lower bound on the optimum for that instance, such as the value of a relaxation, and report the observed cost divided by it. That converts anecdote into an instance-wise bound you can publish alongside the contractual one, and it also tells you when a run is genuinely far from optimal rather than merely unusual.
go deeper
Understand the distinction being drawn: a proven factor applies to every input, while a measurement applies only to the inputs that were measured.
Explain why running both and returning the better answer keeps the proven factor intact, and why that removes most of the apparent trade-off at negligible cost.
Show how to certify a single run: compute a lower bound on the optimum for that instance and divide, so the reported ratio is conservative and independently checkable.
Own the commitment itself. Decide what the contract must survive — adversarial inputs, distribution shift, tenfold growth — and separate the proven ceiling from the historical expectation in everything you publish.
## Two kinds of evidence, routinely confused The decision looks like a choice between algorithms; it is really a choice between **what you can defend**. - The **proven ratio** says: for every admissible input, including ones that do not exist yet, cost is at most twice the optimum. It is scale-free, distribution-free and adversary-proof. It is also pessimistic — the worst case may be a contrived instance nobody will ever submit. - The **measured closeness** says: across last quarter's inputs, the gap to a computed reference was around three percent. It is informative about that distribution and silent about every other one. A new region, a pricing change, a tenfold growth in sites, or an input crafted by someone gaming the system all invalidate it without any bug being introduced. A written commitment is a statement about the future, and only the first kind of evidence is about the future. ## The move that avoids the trade-off The question is usually framed as either/or, and the strongest answer refuses the frame. For a minimisation objective: 1. Run the guaranteed algorithm and the heuristic on the same input. 2. Return whichever answer is cheaper. The combined procedure inherits the guarantee — its output is never worse than the guaranteed algorithm's, so it is still within a factor of two — and in the ordinary case it returns the heuristic's better answer. The cost is one extra polynomial-time run, which is usually negligible against the value of being able to promise anything at all. This works because the guarantee is an upper bound on cost: taking a minimum can only help. (The mirror argument holds for maximisation, taking the larger value.) ## Certifying each run instead of trusting the average A worst-case factor is coarse; what operators actually want to know is "how good was *this* run?". You can answer that without solving the problem, by computing a **lower bound** on the optimum for the instance at hand and dividing. - Any relaxation of the problem that is solvable in polynomial time gives such a bound for a minimisation objective: relaxing constraints can only lower the optimum. - **Linear-programming duality** makes this practical and auditable: any feasible solution to the dual is a valid lower bound on the relaxed optimum, which is itself a lower bound on the true optimum. The bound is checkable by a third party without rerunning anything. - The reported number, cost divided by the bound, is an **upper estimate of the true ratio** for that run, because the denominator is at or below the optimum. This gives you three tiers to talk about, and they should be named separately rather than blended: | Tier | Scope | What it is good for | |---|---|---| | Proven worst-case factor | every possible input | the contractual ceiling | | Per-run certified ratio | this one input | operational reporting, alerting on bad runs | | Historical measured gap | one past distribution | capacity planning, expectation setting | ## Questions to settle before committing 1. **Who supplies the inputs?** If an external party or an incentive-driven process does, assume adversarial-ish inputs and rely only on the proven factor. 2. **What is the consequence of a breach?** A ceiling used for budgeting tolerates optimism; one attached to a penalty does not. 3. **How stable is the input distribution?** Historical evidence decays; if the shape of the fleet changes quarterly, last quarter's three percent is nearly worthless as a promise. 4. **Is the objective the real one?** A tight ratio on a proxy objective can be worse in practice than a loose ratio on the objective that matters. Guarantees compose badly across a redefinition of the objective. 5. **What happens when the bound is not met?** Certification lets you detect it per run; without a lower bound you will never know. ## The posture to argue for Commit the proven factor, run the combination so that typical behaviour is as good as the heuristic's, certify each run against a lower bound, and report the historical distribution separately as information rather than as a promise. That separation is the whole of the judgment: **promises come from proofs, expectations come from measurements**, and publishing the second as the first is the failure mode this question is testing for.
- Why does returning the cheaper of the two answers preserve the factor of two?Because the guarantee is an upper bound on cost. The combined output is never more expensive than the guaranteed algorithm's output, which is already at most twice the optimum, so the combination satisfies the same bound. For a maximisation objective the same reasoning applies to taking the larger value.
- How do you report a per-run ratio without knowing the optimum?Divide the returned cost by a computable lower bound on the optimum for that instance, typically the value of a relaxation or any feasible dual solution. Because the denominator cannot exceed the optimum, the reported figure is an upper estimate of the true ratio — a conservative, auditable statement about that single run.
- When is the heuristic's historical evidence the better basis for a decision?When the decision is internal and reversible — capacity forecasting, setting expectations, choosing a default — and the input distribution is stable and self-supplied. It stops being a basis the moment the number leaves the building as a commitment, or the inputs start coming from somewhere you do not control.
saying these in an interview costs you the question
- Publishes a measured average gap as if it were a guarantee.
- Treats the choice as either the guarantee or the heuristic, never both.
- Assumes future inputs resemble the quarter that was measured.
- Reports a per-run ratio against an unstated or invalid reference value.
- Believes a proven factor implies the algorithm performs worse in practice.