- Atlas
- Computer Science
- Approximation Algorithms
Approximation Algorithms
Many of the optimization problems that matter most—routing delivery trucks, scheduling factory machines, packing items into bins, assigning frequencies to transmitters—share a frustrating property: they are NP-hard.
8 frameworks, from 1972 to today · Algorithms · Computer Science
- Combinatorial approximation 1972-Present
- Polynomial-time approximation scheme 1975-Present
- LP rounding and primal-dual 1982-Present
- Hardness of approximation 1991-Present
- Semidefinite programming rounding 1995-Present
- Resource-constrained approximation 2000-Present
- Unique games conjecture 2002-Present
- Fine-grained approximation 2010-Present
Overview
Many of the optimization problems that matter most—routing delivery trucks, scheduling factory machines, packing items into bins, assigning frequencies to transmitters—share a frustrating property: they are NP-hard123. No efficient algorithm is known that always finds the optimal solution, and under the widely believed conjecture that P ≠ NP, none exists1. Approximation algorithms are the field's response to this hard truth1. Rather than insisting on the best possible answer, they promise an answer provably close to the best, computable quickly. The measure is the approximation ratio: for a minimization problem, an algorithm is a ρ-approximation if its output costs at most ρ times the optimum on every input; for maximization, at least 1/ρ times the optimum1. The history of the field is the story of how this compromise was turned from a collection of clever tricks into a theory—one that can not only construct good approximations but also prove that, for some problems, no substantially better approximation exists unless $P = NP$.
Greedy beginnings and the combinatorial era
The earliest approximation algorithms grew out of the greedy habit: build a solution step by step, always taking the locally best option. For the set cover problem—choose the fewest sets whose union covers everything—the natural greedy rule picks at each step the set covering the most uncovered elements. In the late 1970s, David Johnson and, independently, László Lovász and others analyzed this rule and showed it achieves a ratio of about ln n, where n is the number of elements. The analysis is a small gem: after k greedy steps, if anything remains uncovered, each remaining set covers at least a 1/k fraction of what is left, so the uncovered mass shrinks geometrically, and the harmonic series ln n emerges.
Combinatorial approximation flourished in the 1970s around the emerging theory of NP-completeness4. For the traveling salesman problem on a metric (distances obeying the triangle inequality), Nicos Christofides in 1976 gave an algorithm—build a minimum spanning tree, add a minimum matching on its odd-degree vertices, shortcut the resulting tour—guaranteed within 3/2 of optimal, a bound that stood unbeaten for nearly half a century. For bin packing, simple first-fit and first-fit-decreasing rules were shown to use at most about 11/9 and 11/9 times the optimal number of bins respectively in the early 1970s. For vertex cover, taking both endpoints of a maximal matching gives a factor-2 approximation in a single line1. These results established the field's early style: a clean combinatorial idea, a worst-case argument, a constant or logarithmic ratio.
Linear programming, rounding, and the primal-dual turn
A second wave reframed approximation through linear programming (LP)1. Many combinatorial problems can be written as integer programs—linear objectives and constraints with variables forced to be 0 or 1—which are hard to solve5. Relax the integrality requirement and the problem becomes an LP, solvable in polynomial time5. The art is then rounding: converting the fractional LP solution back into an integral one without losing too much1.
The paradigm crystallized in the 1980s and 1990s. For set cover, LP rounding recovers the same logarithmic guarantee as greedy5. For scheduling on unrelated machines, Lenore Blum, David Karger, and others in the late 1990s used LP rounding to get constant-factor approximations. The primal-dual method, imported from combinatorial optimization, offered a way to design approximation algorithms without ever solving the LP explicitly: grow dual variables until constraints become tight, then round. It produced elegant algorithms for facility location and network design, notably in the work of Kamal Jain and Vijay Vazirani in the late 1990s and early 2000s.
The decisive escalation came with semidefinite programming (SDP), a generalization of LP over matrices6. In 1995, Michel Goemans and David Williamson applied SDP to the max-cut problem—partition the vertices of a graph to maximize edges crossing the partition—and achieved a ratio of about 0.878, beating the trivial 1/2. The technique was geometric: represent each vertex as a vector, solve the SDP, then cut the sphere with a random hyperplane. The analysis used a closed-form integral for the expected angle between random vectors. Max-cut became the emblem of a new era in which sophisticated convex optimization and probabilistic analysis combined to crack problems that had resisted combinatorial attack.
The wall of hardness
As algorithms improved, a complementary question sharpened: how good can an approximation be? The answer came from probabilistically checkable proofs (PCPs). The PCP theorem, proved by Sanjeev Arora, Shafi Goldwasser, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy in the early 1990s, showed that every NP statement has a proof checkable by reading only a constant number of randomly chosen bits. Its algorithmic consequence, developed by Arora and others around 1992–1998, is that many optimization problems are hard to approximate: unless $P = NP$, no polynomial-time algorithm can beat certain ratios.
The landmark results: Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy (1992) and, independently, Uriel Feige, Shafi Goldwasser, László Lovász, Shmuel Safra, and Mario Szegedy (1991–1996) established inapproximability for set cover and other problems; Johan Håstad in 1997 and 2001 gave sharp results showing that for some problems even tiny improvements over trivial ratios are NP-hard. The field now had two frontiers: upper bounds from algorithm design and lower bounds from complexity theory, and the most satisfying results were those where the two met—as with set cover, where the ln n greedy ratio matches the hardness threshold up to lower-order terms.
Polynomial-time approximation schemes
For some problems, hardness of approximation does not apply: one can get arbitrarily close to optimal, at a cost in running time. A polynomial-time approximation scheme (PTAS) is an algorithm that, given any ε > 0, finds a (1+ε)-approximation in time polynomial in the input size (though possibly exponential in 1/ε)7. A fully polynomial-time approximation scheme (FPTAS) runs in time polynomial in both input size and 1/ε8.
The classic example is the knapsack problem: in the 1970s, Oscar Ibarra and Chul Kim, and independently Sartaj Sahni, gave FPTASs based on rounding item values and dynamic programming. For Euclidean traveling salesman and related geometric problems, Arora and Joseph Mitchell independently in 1996 gave PTASs using geometric dissection—cutting the plane into cells and bounding crossings. The discovery that geometry permits near-optimal solutions while general metrics resist them (the metric TSP has no PTAS unless $P = NP$) was a striking lesson in how structure governs approximability.
The unique games conjecture and the modern landscape
Around 2002, Subhash Khot proposed the Unique Games Conjecture (UGC): a statement about the hardness of a particular constraint-satisfaction problem in which each constraint is a bijection between two variables' values. If true, the UGC would imply optimal inapproximability results for a wide range of problems, often matching the best known algorithms. The conjecture became a organizing principle for the field: researchers proved conditional hardness results ("assuming UGC, no algorithm beats ratio ρ") and designed algorithms matching those thresholds. The Goemans–Williamson max-cut ratio, for instance, is conjectured optimal under UGC. Whether the conjecture is true remains one of the central open problems.
In parallel, the field expanded beyond the classical sequential model. Streaming and sublinear settings ask what approximations are possible when memory is tiny or only a few queries are allowed; distributed and online models impose locality and ignorance of the future. Fine-grained approximation connects approximation ratios to precise running-time hypotheses such as the Strong Exponential Time Hypothesis, asking not just whether a ratio is achievable in polynomial time but what ratio is achievable in, say, quadratic time. These directions reflect the field's maturation: approximation is no longer only about NP-hardness but about the resource trade-offs of modern computation.
The present
Today approximation algorithms is a mature subfield with a characteristic dual method: design algorithms via greedy, LP/SDP rounding, primal-dual, or local search, and prove matching or near-matching hardness via PCPs and the UGC. The great open questions are the status of the Unique Games Conjecture, the exact approximability of problems where upper and lower bounds still gap (such as the metric TSP, where the Christofides ratio was only improved in 2020 by Karlin, Klein, and Oveis Gharan to slightly below 3/2), and how approximation behaves under the resource constraints—streaming, distributed, fine-grained—that define contemporary computing. The field's founding insight endures: when the best is out of reach, the provably almost-best is a science of its own.
References
- Approximation algorithm (introduction, Structure of approximation algorithms, Performance guarantees, Introduction, Algorithm design techniques), Wikipedia
- Travelling salesman problem, Wikipedia
- Bin packing problem, Wikipedia
- Hardness of approximation (History), Wikipedia
- Linear programming relaxation (introduction, Approximation and integrality gap), Wikipedia
- Semidefinite programming, Wikipedia
- Polynomial-time approximation scheme, Wikipedia
- Fully polynomial-time approximation scheme, Wikipedia
The frameworks of Approximation Algorithms
Each framework is a way of working the field has used: when it held, and the question it answers.
- 1972-Present
Combinatorial approximation
How close to optimal can a fast combinatorial algorithm get?
- 1975-Present
Polynomial-time approximation scheme
When can we get arbitrarily close to optimal in polynomial time?
- 1982-Present
LP rounding and primal-dual
How can linear programs be rounded to integral solutions?
- 1991-Present
Hardness of approximation
Which approximation ratios are impossible unless P equals NP?
- 1995-Present
Semidefinite programming rounding
How can matrix relaxations yield better approximation ratios?
- 2000-Present
Resource-constrained approximation
What approximations are possible under tight memory or time budgets?
- 2002-Present
Unique games conjecture
Does a certain constraint problem's hardness explain optimal ratios?
- 2010-Present
Fine-grained approximation
What approximation ratio is achievable in a given running time?
How the ideas connect
Each arrow runs from an earlier idea to the later one it shaped. The list below says what passed between them.
Semidefinite programming rounding grew out of LP rounding and primal-dual
Semidefinite programming rounding was a direct generalization of the LP-rounding paradigm: Goemans and Williamson replaced linear relaxations with matrix relaxations and rounded vector solutions by random hyperplanes, keeping the relax-and-round structure intact.
Carried by Michel Goemans; David Williamson.
Unique games conjecture grew out of Hardness of approximation
Khot's Unique Games Conjecture was proposed within the PCP/inapproximability program as a sharper hardness assumption, and it was used to derive optimal inapproximability results of the kind the earlier hardness work had pioneered.
Carried by Subhash Khot.
Polynomial-time approximation scheme grew out of Combinatorial approximation
The early combinatorial style of greedy and exchange arguments supplied the design vocabulary that PTAS work refined: Sahni and Ibarra–Kim built FPTASs for knapsack by rounding values and running dynamic programming, a scheme-based extension of the same worst-case combinatorial analysis.
Carried by Sartaj Sahni; Oscar Ibarra; Chul Kim.
LP rounding and primal-dual grew out of Combinatorial approximation
LP rounding for set cover was presented as recovering the same logarithmic guarantee as the greedy combinatorial algorithm, so the LP paradigm grew directly out of the earlier combinatorial analyses and was measured against them.
Fine-grained approximation grew out of Hardness of approximation
Fine-grained approximation carried the inapproximability question from NP-hardness to precise running-time hypotheses such as SETH, asking what ratio is achievable in a given time bound rather than merely in polynomial time.
Unique games conjecture influenced by Semidefinite programming rounding
The Goemans–Williamson SDP algorithm for max-cut became the benchmark that the UGC was framed to explain: Khot conjectured that its 0.878 ratio is optimal, making the SDP rounding result the target of the conditional hardness program.
Carried by Subhash Khot; Michel Goemans; David Williamson.
Beyond the field
Where Approximation Algorithms's ideas came from in other fields, and what they led to there: the strongest 12 of 33 links.
Combinatorial approximation influenced by Combinatorial optimization in Mathematical Optimization
Combinatorial optimization supplied the problem classes (matching, covering, scheduling, TSP) and the polyhedral and LP-based methods that approximation algorithms took up and relaxed. The 1972 work on NP-hardness of combinatorial problems, framed within this tradition, is what made approximation the natural response.
Carried by Combinatorial Optimization (1958); Richard M. Karp.
Polynomial-time approximation scheme grew out of Approximation algorithm in Combinatorial Optimization
The polynomial-time approximation scheme is a refinement of the approximation algorithm: it demands a family of algorithms with a tunable error parameter rather than a single fixed-ratio guarantee. The PTAS concept grew directly out of the approximation-algorithm literature of the early 1970s.
Polynomial-time approximation scheme influenced by NP-completeness in Complexity Theory
NP-completeness, established by Cook and Karp around 1971, is the reason approximation schemes exist: once exact polynomial-time solution is ruled out, one seeks a tunable approximation. The PTAS is defined and motivated entirely within the NP-completeness framework.
Carried by Stephen Cook; Richard M. Karp.
LP rounding and primal-dual grew out of Approximation algorithm in Algorithms
LP rounding and primal-dual methods are a specific technique within approximation algorithms, developed in the early 1980s as a way to obtain and analyse approximation guarantees via linear programs. The framework is a branch grown out of the general approximation-algorithm programme.
LP rounding and primal-dual influenced by Integer and Mixed-Integer Programming in Combinatorial Optimization
Integer and mixed-integer programming supplied the LP relaxations whose rounding and duals define this framework. The primal-dual schema for approximation was adapted from LP duality and the LP/IP relaxation gap central to integer programming.
LP rounding and primal-dual led to Primal-Dual and LP-Based Methods in Online Algorithms
Primal-dual and LP-based methods for online algorithms grew directly out of the offline LP rounding and primal-dual techniques for approximation algorithms. The online versions adapted the offline primal-dual schema to competitive analysis.
Hardness of approximation reacted against Approximation algorithm in Algorithms
Hardness of approximation arose as a response to the approximation-algorithm programme: PCP theorems showed that many approximation ratios achieved by known algorithms were essentially optimal, closing off further improvement. The field defined itself by these negative results against the positive approximation literature.
Semidefinite programming rounding influenced by Randomized rounding in Randomized Algorithms
Randomized rounding, introduced by Raghavan and Thompson in 1987, is the direct ancestor of semidefinite-programming rounding: the Goemans-Williamson max-cut algorithm replaced the LP with an SDP and rounded the resulting vectors randomly. The technique passed directly from randomized LP rounding to SDP rounding.
Carried by Prabhakar Raghavan; Clark Thompson; Michel Goemans.
Semidefinite programming rounding grew out of Approximation algorithm in Algorithms
Semidefinite-programming rounding is a branch of approximation algorithms, introduced by Goemans and Williamson in 1995 for max-cut. It grew out of the general approximation-algorithm programme as a new relaxation-and-rounding technique.
Carried by Michel Goemans; David Williamson.
Resource-constrained approximation grew out of Approximation algorithm in Combinatorial Optimization
Resource-constrained approximation is a branch of approximation algorithms that adds budget or resource constraints to the optimisation, growing out of the standard approximation framework. It refines the approximation-algorithm programme to constrained settings such as budgeted and knapsack-constrained problems.
Unique games conjecture influenced by Hardness of Approximation in Combinatorial Optimization
The unique games conjecture was proposed by Subhash Khot as a strengthening of the PCP-based hardness-of-approximation programme, aiming to explain the exact inapproximability thresholds found for problems like Max Cut and Vertex Cover. It built directly on the hardness results and PCP machinery developed in the 1990s.
Carried by Subhash Khot.
Unique games conjecture influenced by Hardness of Approximation in Complexity Theory
Khot's unique games conjecture grew out of the complexity-theoretic hardness-of-approximation tradition, notably the PCP theorem and the optimal inapproximability results of the 1990s. It was framed as a conjecture whose truth would settle the approximability of many optimization problems.
Carried by Subhash Khot; Probabilistically Checkable Proofs and the Hardness of Approximation (1992).

Approximation Algorithms is a planet in Nousfarer
Its city has a tower for each of these 8 frameworks. Land, walk in, and climb one concept at a time.
Land on Approximation AlgorithmsRelated fields
Fields its ideas are linked to
- Combinatorial Optimization 12 links
- Algorithms 5 links
- Complexity Theory 4 links
- Graph Algorithms 2 links
- Online Algorithms 2 links
- Parameterized Algorithms 2 links
- Mathematical Optimization 2 links
- Randomized Algorithms 1 link
- Operations Research 1 link
- Applied Mathematics 1 link
- Combinatorics 1 link
More in Algorithms
- Algorithms
- Computational Geometry
- Data Structures
- Distributed Algorithms
- Graph Algorithms
- Online Algorithms
- Parallel Algorithms
- Parameterized Algorithms
- Randomized Algorithms
- Streaming Algorithms
- String Algorithms
See where Approximation Algorithms sits on the Map of Human Knowledge