Coping With Intractability

A 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.

The incumbent is the best complete plan found so far, and its cost is the cut-off. The bounding function computes an optimistic cost for everything still reachable in a subtree; if that is no better, the subtree is discarded unexplored.

The exponent's home decides it. In 2^k times n only the small conflict count k sits in an exponent, so a bigger graph costs a linear factor more. In n^k the graph itself is raised to k, so growth is fatal.

Routine, hard, or impossible. Routine needs a named polynomial method that fits; hard needs a known NP-complete problem sitting inside the requirement; impossible needs the shape of a question about what an arbitrary program does at runtime.

Every edge must be covered, so at least one of its two endpoints is in the cover: a forced two-way branch. Each branch spends one unit of the budget k, so the tree is at most k deep and has at most 2^k leaves.

Both schemes take an accuracy parameter and return a solution within that fraction of optimal. A PTAS is polynomial in the input size for each fixed accuracy, but its exponent may blow up as accuracy tightens; an FPTAS is polynomial in the input size and in the reciprocal of the accuracy together.

The tree an exhaustive search walks is not fixed by the problem; it is created by the order decisions are made. Ordering that forces contradictions near the root cuts enormous subtrees early, while a poor order discovers the same contradictions at the leaves.

Look for structure the general problem lacks: an input shaped as a tree or a line of intervals, two of something where the hard version needs three, or a genuinely small integer bound. Each turns open search into forced or tabulated work.

The triangle inequality lets an algorithm skip an already-visited site without paying more, so a cheap structure spanning all sites can be converted into a tour of comparable cost. With arbitrary costs, missing connections can be priced so high that any constant-factor approximation would decide Hamiltonicity.

A mature solver contributes decades of search engineering you will not reproduce: constraint propagation, conflict analysis that learns a clause and jumps back, activity-driven branching and restarts. Your remaining job is the encoding, and the encoding then becomes the thing to get right.

It moves the whole graph out of the expensive factor. Polynomial-time reduction rules return an equivalent instance of size bounded by k, so the exponential search afterwards runs on something the size of k squared, not on the graph.

A usable verdict names which version of the problem was triaged, the evidence tier behind it — matched against a known problem, or proved — the input sizes and exactness it assumes, and what would overturn it. The label alone is not a plan.

Only 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.

Decide by what has to be defended. A deadline-stopped exact search returns a plan plus a proven interval containing the optimum; a local-search heuristic returns a plan and no claim at all. Where nobody needs the certificate, the heuristic scales further.

Ask what enforces the dozen. A parameterized plan is sound when a specification or a physical limit caps the parameter, measured in production and guarded at runtime; if only observed data caps it, the design needs a documented fallback for the day it does not.

APX-hardness rules out an approximation scheme: unless P = NP there is a fixed threshold factor that no polynomial-time algorithm can beat, so accuracy cannot be dialled arbitrarily close to optimal. It does not rule out a constant factor, which such problems often have.

Each half has only 2^20 subsets, so both are enumerated cheaply. One half is stored in a structure keyed by its partial contribution, and each subset of the other half is matched against it. The exponent halves; storing 2^20 entries is the price.

Brute force over all k-subsets gives n^k, which is XP, and nothing better in shape is known. Finding a k-clique is hard for the class W[1], so an f(k) times polynomial algorithm would collapse W[1] into FPT - widely disbelieved.

Commit to the reversible option: build behind a boundary, guard the input sizes you can defend, and record the unresolved question where the requirement lives. The two wrong calls cost differently, and the expensive one surfaces late, under real data.