Loading field map
Many of the most practically important optimization problems are NP-hard, meaning that unless P = NP, no polynomial-time algorithm can solve them exactly. Faced with this barrier, computer scientists had a choice: abandon optimality or abandon generality. Approximation algorithms take the second path. They sacrifice exactness for efficiency, producing solutions that are provably close to optimal in polynomial time. The central tension of the subfield is the interplay between what can be achieved (upper bounds from algorithm design) and what cannot be achieved (lower bounds from hardness of approximation). This tension has driven the development of four major frameworks, each responding to a different facet of the challenge.
The earliest approximation algorithms emerged alongside the formalization of NP-completeness. Researchers realized that for many NP-hard problems, a simple, fast algorithm could guarantee a solution within a fixed factor of the optimum. The key measure became the approximation ratio: for a minimization problem, an algorithm with ratio ρ always returns a solution with cost at most ρ times the optimal cost. For a maximization problem, it returns a solution with value at least 1/ρ of the optimal value.
A canonical example is the vertex cover problem: given an undirected graph, find the smallest set of vertices that touches every edge. A greedy algorithm that repeatedly picks an edge and includes both its endpoints achieves a 2-approximation. This is not just a heuristic; it is a provable guarantee. Other foundational techniques included LP rounding (solving a linear programming relaxation and rounding the fractional solution to an integer one) and local search (iteratively improving a candidate solution until a local optimum is reached). The classic work of Lenstra, Shmoys, and Tardos on scheduling on unrelated parallel machines used LP rounding to achieve a 2-approximation, a result that remains influential.
By the late 1980s, researchers had developed approximation algorithms for a wide range of problems, including the traveling salesman problem (TSP), set cover, and bin packing. The field was thriving, but a fundamental question remained unanswered: how good could these approximations get? For some problems, like vertex cover, the best known ratio was stuck at 2. Was that because better algorithms were undiscovered, or because no better ratio was possible? Answering that question required a new framework.
The 1990s brought a revolution. The PCP theorem (Probabilistically Checkable Proofs) showed that every NP problem can be verified by a randomized algorithm that reads only a constant number of bits of a proof. This abstract result had a concrete consequence for approximation: it provided a way to prove that certain approximation ratios are impossible unless P = NP. The connection is subtle but powerful. By encoding an NP-complete problem into a gap problem—where yes-instances and no-instances are separated by a gap in the objective value—the PCP theorem implies that distinguishing between the two cases is NP-hard. This translates directly into an inapproximability threshold.
For example, the metric TSP admits a 1.5-approximation via Christofides' algorithm. The PCP theorem, combined with subsequent reductions, has been used to show that approximating metric TSP within a factor of 123/122 ≈ 1.0082 is NP-hard. The gap between 1.0082 and 1.5 remains open, but the existence of a threshold is now certain. Similarly, for vertex cover, the PCP theorem led to a proof that no polynomial-time algorithm can achieve a ratio better than 1.3606 unless P = NP, and under the stronger Unique Games Conjecture, the threshold is exactly 2. This explains why the simple 2-approximation had resisted improvement for decades.
PCP-based hardness did not replace classical approximation algorithms; it transformed them. Algorithm designers now work with a clear target: match the inapproximability threshold or, failing that, narrow the gap. The framework also introduced a new style of research: proving lower bounds on approximation ratios became as central as designing algorithms. The two activities are now symbiotic, with each new upper bound motivating a search for a matching lower bound, and vice versa.
While classical approximation algorithms assume that the entire input is available at once, many real-world problems require decisions to be made sequentially without knowledge of the future. This is the domain of online approximation, where the algorithm receives a request, must respond immediately, and only later sees the next request. The standard measure is the competitive ratio: the worst-case ratio of the algorithm's cost to the optimal offline cost (the cost of the best solution in hindsight).
A classic example is the paging problem: a cache of size k can hold k pages; when a new page is requested that is not in the cache, one page must be evicted. The optimal offline algorithm (known as Belady's algorithm) evicts the page that will be requested farthest in the future. An online algorithm, however, cannot see the future. The deterministic algorithm LRU (least recently used) achieves a competitive ratio of k, which is optimal for deterministic online algorithms. Randomized algorithms can do better: the marking algorithm achieves a competitive ratio of 2Hk (where Hk is the k-th harmonic number), which is optimal for randomized algorithms.
Online approximation differs from classical approximation in its problem setting, not just its measure. The algorithm must be designed to handle uncertainty, and the competitive ratio compares against a stronger adversary (the offline optimum). This framework coexists with classical approximation; many problems have both offline and online variants, and techniques from one sometimes inform the other. For instance, the concept of a potential function used in online analysis has roots in amortized analysis from classical algorithms.
A different response to NP-hardness is to accept exponential time but restrict it to a small parameter of the input. Fixed-parameter tractable (FPT) approximation combines this idea with approximation. The goal is to design algorithms that run in time f(k) · n^{O(1)}, where k is a parameter (such as treewidth, solution size, or the number of vertices in a feedback vertex set), and achieve an approximation ratio that may depend on k or be constant.
For example, the k-center problem asks for the smallest radius r such that k balls of radius r cover all points. This problem is NP-hard, but if the number of centers k is small, an FPT approximation algorithm can find a solution with radius at most (1+ε) times the optimal in time exponential only in k. This framework extends classical approximation by adding a parameter dimension: when the parameter is small, the algorithm is efficient; when the parameter is large, the problem may be intractable even to approximate.
FPT approximation does not replace classical methods; it complements them. Many classical approximation algorithms are already FPT with respect to natural parameters (e.g., the 2-approximation for vertex cover is FPT with parameter k = solution size). The synergy runs deeper: parameterized techniques, such as kernelization and bounded-treewidth dynamic programming, can be used to design approximation schemes for problems that resist classical approaches. For instance, the Euclidean TSP admits a polynomial-time approximation scheme (PTAS) using geometric partitioning, but for general graphs, no PTAS exists unless P = NP. FPT approximation provides a middle ground: a PTAS parameterized by treewidth exists for many problems on graphs of bounded treewidth.
Today, all four frameworks are active and interact in complex ways. Classical approximation algorithms remain the workhorse for problems where constant-factor guarantees are known and inapproximability thresholds are understood. PCP-based hardness continues to produce sharper lower bounds, often using the Unique Games Conjecture as a stronger assumption. Online approximation has expanded into areas like learning-augmented algorithms, where a machine learning prediction is used to improve the competitive ratio. FPT approximation is increasingly used to design approximation schemes for problems that are hard to approximate in general but become tractable on structured inputs.
A major area of agreement across frameworks is the centrality of the approximation ratio as a measure of quality. All frameworks accept that exactness is often impossible and that provable guarantees are the gold standard. The main disagreement is about the appropriate setting: classical and PCP-based work assume full knowledge of the input, online assumes sequential uncertainty, and FPT assumes a small parameter. These are not competing views of the same problem but different lenses for different problem classes.
A concrete example of cross-framework interaction is the k-median problem in metric spaces. Classical approximation algorithms achieve a ratio of about 2.6 via LP rounding. PCP-based hardness shows that no ratio better than 1+2/e ≈ 1.736 is possible unless P = NP. Online versions of k-median have been studied with competitive ratios that depend on the number of facilities. FPT approximation gives a PTAS when the number of facilities k is small. A researcher working on k-median today might use all four frameworks: classical for the best known upper bound, PCP for the lower bound, online for streaming or dynamic settings, and FPT for small k.
The field continues to evolve. Open problems include closing the gap between upper and lower bounds for classic problems like metric TSP and vertex cover, understanding the power of randomization in online approximation, and developing FPT approximation schemes for problems with multiple parameters. The tension between what can be achieved and what cannot remains the engine of progress.