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

still a working view ended · each leads to its entry below

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

  1. Approximation algorithm (introduction, Structure of approximation algorithms, Performance guarantees, Introduction, Algorithm design techniques), Wikipedia
  2. Travelling salesman problem, Wikipedia
  3. Bin packing problem, Wikipedia
  4. Hardness of approximation (History), Wikipedia
  5. Linear programming relaxation (introduction, Approximation and integrality gap), Wikipedia
  6. Semidefinite programming, Wikipedia
  7. Polynomial-time approximation scheme, Wikipedia
  8. 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.

  1. 1972-Present

    Combinatorial approximation

    How close to optimal can a fast combinatorial algorithm get?

    Fly to its tower in Nousfarer

  2. 1975-Present

    Polynomial-time approximation scheme

    When can we get arbitrarily close to optimal in polynomial time?

    Fly to its tower in Nousfarer

  3. 1982-Present

    LP rounding and primal-dual

    How can linear programs be rounded to integral solutions?

    Fly to its tower in Nousfarer

  4. 1991-Present

    Hardness of approximation

    Which approximation ratios are impossible unless P equals NP?

    Fly to its tower in Nousfarer

  5. 1995-Present

    Semidefinite programming rounding

    How can matrix relaxations yield better approximation ratios?

    Fly to its tower in Nousfarer

  6. 2000-Present

    Resource-constrained approximation

    What approximations are possible under tight memory or time budgets?

    Fly to its tower in Nousfarer

  7. 2002-Present

    Unique games conjecture

    Does a certain constraint problem's hardness explain optimal ratios?

    Fly to its tower in Nousfarer

  8. 2010-Present

    Fine-grained approximation

    What approximation ratio is achievable in a given running time?

    Fly to its tower in Nousfarer

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.

Combinatorial approximationPolynomial-time approximation schemeLP rounding and primal-dualHardness of approximationSemidefinite programming roundingResource-constrained approximationUnique games conjectureFine-grained approximation

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.

A city in Nousfarer: a red-carpeted stair climbing terraces to a crowned tower on an acropolis, more towers round it, forest and snowy mountains beyond.
A city in Nousfarer, the game played in the browser.

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 Algorithms

Related fields

Fields its ideas are linked to

More in Algorithms

See where Approximation Algorithms sits on the Map of Human Knowledge