When would you ship a greedy heuristic you know is suboptimal instead of the correct DP?

## Two decisions, not one Paradigm *analysis* asks what the problem's structure permits: independent pieces, a safe local choice, or repeated subproblems over a compact state. Paradigm *selection for production* asks something else entirely — what we can afford to run, operate and maintain. A lead is expected to keep these separate and to be explicit when the second one overrides the first. Shipping a known-suboptimal rule is a legitimate engineering decision. Shipping one *without knowing it is suboptimal* is negligence. The whole of this answer is the difference between those. ## The inputs to the decision **What does a suboptimal answer actually cost?** This is the first question and it decides most cases. If the output is an internal plan that is re-derived hourly, a small gap is noise. If it is a price shown to a customer, a fee we invoice, or an allocation someone is entitled to, then a gap is not an approximation — it is a wrong number, potentially a contractual or regulatory one, and the answer is no regardless of latency. **How big is the gap, on the traffic we actually get?** Worst-case analysis is the wrong instrument here; a rule with a terrible adversarial bound may be exact on 99.9% of real inputs. Get the distribution: run the exact method and the heuristic side by side over a captured slice of production traffic, offline where latency does not matter, and plot the gap. The tail is the number that matters, along with how the tail correlates with input size. **What does the exact method cost to run?** Not just asymptotics — the per-request latency at the sizes you see, the memory the table holds per concurrent request, and what that multiplies to across a fleet. A table that is fine on one machine can be the reason you need three times the nodes. **What does it cost to maintain?** A recurrence with a subtle state definition is code that one person understands. If that person leaves, every change becomes risky. This is a real cost, it belongs in the decision, and it is the one most often left unsaid because it sounds unrigorous. It is not — the probability of a future incorrect edit is a genuine risk term. ## The shape the answer usually takes Rarely all-or-nothing. The defensible structures are: - **Threshold.** Exact below an input size chosen from the latency budget, heuristic above it. Most traffic gets the exact answer; the tail gets a fast approximate one. The threshold is a tuned parameter with a stated basis, not a round number someone liked. - **Two tiers.** Heuristic on the request path for immediate response, exact recomputation in a batch or asynchronous pass that corrects the record. Works when the answer can be revised. - **Heuristic with a guard.** Ship the rule, but compute a bound or a sanity check cheaply and escalate the cases that look bad. In all three, the exact solver stays in the repository as a **test oracle**: it is what the heuristic is diffed against in tests and what you re-run when someone proposes tightening the rule. Deleting it because "we do not use it in production" is how the gap becomes unmeasurable a year later. ## Guardrails that must accompany the decision Write down the gap you are accepting, as a number, in the place the decision is recorded. Emit a metric that lets you observe it — sampled comparisons against the exact method in the background, or a proxy such as the frequency of the input patterns known to trigger the gap. Alert when it drifts, because input distributions move: the sparse-then-dense pattern that was rare last year may be the shape of your traffic after a product change. A heuristic justified by a measurement in a document nobody re-runs is a heuristic justified by nothing. ## When to refuse Refuse when the number is a promise: a quoted price, a billed amount, a regulated allocation, anything a customer or auditor can hold you to. Refuse when the gap is unmeasurable because no exact reference exists to compare against — then you are guessing, not trading. And refuse when the pressure comes from a deadline rather than a constraint: "the exact one is harder to write" is not a latency budget, and a rewrite is cheaper now than after the wrong numbers have accumulated downstream. ## What makes this a lead's call An engineer can compute both answers. What makes it a leadership decision is that it prices correctness against latency, cost and team capability, commits the organisation to living with a known error, and puts the monitoring in place that makes the commitment honest. The answer an interviewer wants is not "yes, ship the fast one" or "never approximate" — it is the framework, the measurement, and the line you would not cross.