Solutions for NP-hard Problems — Epoche C1
What a 2-approximation is actually telling you There is an algorithm for the Vertex Cover problem — given a graph, find the smallest set of vertices touching every edge — that never returns a set more than twice the size of the smallest one, and that consists of nothing more than repeatedly picking an uncovered edge and taking both of its endpoints. The received attitude towards such an algorithm is that it is a concession: the exact answer is out of reach, so one settles for twice the optimum. The argument of this essay is that the attitude misreads the situation, because for Vertex Cover it is also known — under a conjecture that has been studied intensively for two decades — that no polynomial-time algorithm can guarantee a factor of $2 - \varepsilon$ for any fixed $\varepsilon > 0$. If that is right, the crude algorithm is not a compromise at all. It is at the ceiling. Two definitions are needed before that claim can be made precise, and the first requires correcting something the compressed version of this essay asserted. A problem is NP-hard if every problem in NP — the class of decision problems whose 'yes' answers admit a proof checkable in polynomial time — can be transformed into it by a polynomial-time reduction. NP-hardness is thus a statement about reducibility, not, as is often loosely said, about our failure so far to find a fast algorithm; a proof that $\mathrm{P} = \mathrm{NP}$ would leave every NP-hard problem NP-hard while making them all easy. What follows from NP-hardness is conditional: unless $\mathrm{P} = \mathrm{NP}$, no polynomial-time algorithm solves the problem exactly. The classic catalogue of such problems, and of the reductions establishing their hardness, is Garey and Johnson's Computers and Intractability (1979). The second definition concerns what one settles for instead. For a minimisation problem, an algorithm is an $\alpha$-approximation if on every instance the cost $C_{\mathrm{alg}}$ of its output satisfies $C_{\mathrm{alg}} \le \alpha\, C_{\mathrm{opt}}$, where $C_{\mathrm{opt}}$ is the cost of a true optimum; for maximisation the corresponding requirement is $C_{\mathrm{alg}} \ge C_{\mathrm{opt}}/\alpha$. In both conventions $\alpha \ge 1$, and $\alpha = 1$ means exactness. The interesting quantity in what follows is not $\alpha$ alone but the pair consisting of the best $\alpha$ any known algorithm achieves and the best $\beta$ that can be proved unachievable — the upper and lower ends of a bracket around the truth. The easy end: problems whose gap can be driven towards zero Begin with the class in which the received attitude is most nearly correct, because there the gap really can be made negligible. A problem admits a polynomial-time approximation scheme (PTAS) if for every fixed $\varepsilon > 0$ there is a $(1+\varepsilon)$-approximation running in time polynomial in the input size $n$. It admits a fully polynomial-time approximation scheme (FPTAS) if the running time is additionally polynomial in $1/\varepsilon$ — a much stronger demand, since a PTAS is permitted a running time such as $n^{1/\varepsilon}$, which is polynomial for each fixed $\varepsilon$ and useless for small ones. The Knapsack problem — choose a subset of items of given sizes and values, fitting a capacity, maximising total value — has an FPTAS, and the construction shows exactly where the two polynomials come from. Knapsack has an exact dynamic program indexed by achievable value rather than by size: for each prefix of the items and each attainable total value $V$, record the least capacity needed to reach $V$. Since no total value exceeds $n v_{\max}$, where $v_{\max}$ is the largest single value, the table has $O(n \cdot n v_{\max})$ entries and the algorithm runs in $O(n^2 v_{\max})$ time. This is pseudo-polynomial : polynomial in the numerical magnitude of the input rather than in its length, since $v_{\max}$ written in binary occupies only $\log v_{\max}$ bits. The scheme removes the dependence on magnitude by rounding. Set $K = \varepsilon v_{\max}/n$ and replace each value by $v_i' = \lfloor v_i/K \rfloor$. Each item's value is understated by less than $K$, and a solution contains at most $n$ items, so the optimum of the rounded instance, measured back in original units, understates the true optimum by at most $nK = \varepsilon v_{\max}$. Discarding at the outset any item that does not fit alone, the optimum is at least $v_{\max}$, so the loss is at most $\varepsilon\,C_{\mathrm{opt}}$. Meanwhile the largest rounded value is $\lfloor v_{\max}/K\rfloor = \lfloor n/\varepsilon \rfloor$, so the dynamic program now runs in $O(n^2 \cdot n/\varepsilon) = O(n^3/\varepsilon)$ time — polynomial in $n$ and in $1/\varepsilon$ separately, which is precisely the definition of an FPTAS. That derivation also explains which problems cannot have one. Garey and Johnson distinguish problems that remain NP-hard when all numbers in the input are bounded by a polynomial in the input length — strongly NP-hard problems — and show that such a problem cannot have an FPTAS unless $\mathrm{P} = \mathrm{NP}$, for the reason that if the optimum value is itself polynomially bounded, then running the scheme with $\varepsilon$ smaller than $1/C_{\mathrm{opt}}$ forces the answer to be exactly optimal, in time still polynomial. Knapsack escapes only because it is NP-hard solely by virtue of large numbers. The Travelling Salesperson Problem restricted to points in the plane is strongly NP-hard and therefore has no FPTAS, yet Arora (1998) showed it does have a PTAS, with running time roughly $n(\log n)^{O(1/\varepsilon)}$. The two facts are consistent, and their consistency is the point: the difference between PTAS and FPTAS is not a technicality but the trace of a structural difference in where the hardness lives. Constant factors, and where the constants come from The second class consists of problems for which the best guarantee is a constant strictly greater than $1$. Constants of this kind are us