Approximation Thresholds for NP-Hard Problems: From the Knapsack Scheme to the 7/8 Barrier — Epoche C1
Knapsack and MAX-3SAT are both NP-hard, and one of them can be solved to within any accuracy you name in polynomial time while the other cannot be solved to within a hair better than the guarantee of a coin toss. A widespread belief holds that NP-hardness forfeits only exactness — that a fast algorithm delivering a decent fraction of the optimum is always available. This review follows the results that tested that belief, from the approximation schemes of the 1970s to the PCP theorem and its sharpest consequence, and shows that what emerges is a classification with provable boundaries: some NP-hard problems can be approximated arbitrarily well, others meet a ceiling, and the exact height of the ceiling is itself a theorem. 1. Four classes of approximability Fix the vocabulary first. An algorithm is a $\rho$-approximation if it always returns a feasible solution within a factor $\rho$ of the optimum — cost at most $\rho \ge 1$ times the optimum when minimising, value at least $\rho \le 1$ times it when maximising — while running in time bounded by a fixed power of the input size $n$. Sorted by the best $\rho$ anyone has achieved, the classical NP-hard problems fall into four groups. Full schemes. For knapsack — pack items of given values and weights to maximise total value under a weight limit — Ibarra and Kim (1975) gave, for every $\varepsilon > 0$, a $(1-\varepsilon)$-approximation running in time polynomial in both $n$ and $1/\varepsilon$. The loss can be made as small as one likes, at a price that grows only polynomially. Constant factor. The travelling salesman problem on metric distances — distances obeying the triangle inequality — admits the ratio-$3/2$ algorithm of Christofides (1976). For MAX-3SAT — satisfy as many clauses as possible, each clause an OR of three literals, a literal being a variable or its negation — a uniformly random assignment already achieves $7/8$. Logarithmic factor. For set cover — cover $n$ elements using as few sets as possible from a given family — the greedy algorithm guarantees roughly $\ln n$ times the optimal number of sets. Nearly nothing. For maximum clique — find the largest set of pairwise adjacent vertices in an $n$-vertex graph — no guarantee remotely comparable is known. Three of those guarantees are short enough to prove here, and the proofs are worth having because the rest of the essay is about their limits. The knapsack scheme. Begin with an exact algorithm indexed by value rather than weight: for each prefix of the items and each attainable total value $V$, record the least weight achieving exactly $V$. With $v_{\max}$ the largest single value, no total exceeds $nv_{\max}$, so the table has $O(n^2 v_{\max})$ entries and is filled in that time. This is pseudo-polynomial : polynomial in the numbers appearing in the input, not in their binary length. Now round. Put $K = \varepsilon v_{\max}/n$ and replace each value by $v_i' = \lfloor v_i/K \rfloor$. The largest rounded value is then $\lfloor n/\varepsilon\rfloor$, so the table shrinks to $O(n^2/\varepsilon)$ entries and the running time to $O(n^3/\varepsilon)$ — polynomial in $n$ and in $1/\varepsilon$, which is what "full scheme" means. The loss is bounded because rounding down discards less than $K$ per item, hence less than $nK = \varepsilon v_{\max}$ in total. Writing $S^{*}$ for the true optimum and $S'$ for the set the rounded computation returns, $v(S') \ge K\,v'(S') \ge K\,v'(S^{*}) \ge v(S^{*}) - nK = \mathrm{OPT} - \varepsilon v_{\max}$, and since a single item is always a feasible packing, $\mathrm{OPT} \ge v_{\max}$, giving $v(S') \ge (1-\varepsilon)\mathrm{OPT}$. Every factor has a reason: $n$ items each lose at most $K$, and the division by $v_{\max}$ is licensed by the one-item solution. Christofides' tour. Take a minimum spanning tree $T$ of the metric. Deleting any edge of an optimal tour leaves a Hamiltonian path, which is a spanning tree, so $\mathrm{cost}(T) \le \mathrm{OPT}$. The vertices of odd degree in $T$ are even in number, since degrees sum to twice the edge count. Let $O$ be that set and let $M$ be a minimum-cost perfect matching on it. Shortcut the optimal tour so that it visits only the vertices of $O$: by the triangle inequality this cycle costs at most $\mathrm{OPT}$, and having an even number of edges it splits into two disjoint perfect matchings on $O$, the cheaper of which costs at most $\mathrm{OPT}/2$. Hence $\mathrm{cost}(M) \le \mathrm{OPT}/2$. In the multigraph $T \cup M$ every vertex has even degree and the graph is connected, so an Eulerian circuit exists, of cost at most $\tfrac{3}{2}\mathrm{OPT}$; shortcutting its repeated vertices cannot raise the cost, again by the triangle inequality. Note where the metric assumption is used: twice, and in both places the bound fails without it. Greedy set cover. Suppose the optimum uses $k$ sets. At any stage with $r$ elements still uncovered, those $k$ sets cover all $r$, so one of them covers at least $r/k$; the greedy choice covers at least as many. The uncovered count therefore falls by a factor $(1-1/k)$ each round, so after $t$ rounds it is below $n(1-1/k)^{t} \le n e^{-t/k}$. Taking $t = k\ln n$ makes this less than $1$, and a count below one is zero. Greedy uses at most $k \ln n$ sets. MAX-3SAT by coin toss. Assign each variable true or false independently and uniformly. A clause of three literals over three distinct variables fails only when all three literals are false, an event of probability $(1/2)^{3} = 1/8$; by linearity of expectation the expected number satisfied is $\tfrac78 m$ for $m$ clauses. The restriction to distinct variables matters and should be stated plainly: for a clause whose literals repeat a variable the probability drops, so the $7/8$ guarantee — and the matching hardness result below — belong to instances in which every clause has exactly three distinct variables. The expectation can be attained deterministically by the method of conditional expectations, fixing the variables