Skip to main content
v2026.11,986 entries · CC-BY 4.0

Approximation Algorithms: Ratios, Worked Examples, Hardness Limits

What an approximation algorithm guarantees, how the two ratio conventions differ, and worked vertex cover and set cover examples with proven hardness limits.

Written and maintained by CASRAI Editorial Board

Published

On this page

An approximation algorithm is a polynomial-time algorithm for an optimisation problem that does not promise the best answer but does promise a provable bound on how far its answer can be from the best one, for every possible input. The bound is called the approximation ratio. A 2-approximation for a minimisation problem, for example, always returns a solution whose value is at most twice the optimum, however adversarial the instance.

What an approximation algorithm is and why researchers use it

Many optimisation problems that arise in research computing, such as covering a set of requirements with as few resources as possible, partitioning a network to maximise a cut, or placing facilities, are NP-hard: no polynomial-time exact algorithm is known for them, and finding one would settle the P versus NP question (see the CASRAI guide to computational complexity). Cornell’s CS 6820 lecture notes on approximation algorithms describe the response: give up on exact optimality and accept a solution that is provably near-optimal, found in polynomial time. The same notes point out that approximation can also pay off when an exact polynomial-time algorithm exists, because the approximate method may be faster, use less space or parallelise better, which matters for very large data.

Chekuri’s UIUC CS583 lecture notes (Fall 2021) give the formal definition: an algorithm A is an α-approximation algorithm for a problem if, for every instance I, the value of the feasible solution that A returns is within a multiplicative factor α of OPT(I), the value of an optimal solution. Two features of that sentence matter in practice.

  • It is a worst-case statement. The ratio is the supremum over all instances, so a single bad instance sets it. The notes also allow α to depend on the instance size, written α(|I|), which is how logarithmic ratios arise.
  • It compares against OPT, which the algorithm never computes. Proofs of a ratio therefore work by bounding OPT from below (for minimisation) or from above (for maximisation) with a quantity the algorithm can control.

The approximation ratio and its two conventions

Papers and course notes do not all write the ratio the same way, and mixing the conventions is the most common reading error. Both sources used for this page state a convention explicitly, and they differ in how they treat maximisation.

Source and convention Minimisation Maximisation Ratio range
Chekuri, UIUC CS583 (Fall 2021): factor of α of OPT ALG ≤ α · OPT ALG ≥ α · OPT α ≥ 1 for minimisation, α ≤ 1 for maximisation
Cornell CS 6820 (2016) and the alternative convention noted in the UIUC notes OPT ≤ ALG ≤ α · OPT ALG ≤ OPT ≤ α · ALG, equivalently ALG ≥ (1/α) · OPT α ≥ 1 for both

Under the first convention a maximisation algorithm that always returns at least half the optimum is a 1/2-approximation; under the second it is a 2-approximation. The two statements are the same guarantee. When you compare ratios across papers, first write each one as an inequality between ALG and OPT, then compare. Hardness results use the same wording, so “no (1 − 1/e − ε)-approximation” (first convention, maximisation) and “no better than a factor e/(e − 1)” (second convention) say the same thing.

Worked example 1: vertex cover by maximal matching

A vertex cover of a graph is a set of vertices that touches every edge; the minimum vertex cover problem asks for the smallest one. Both sources treat it as the introductory example. Chekuri’s notes (section 2.2.1) give a matching-based algorithm, and prove in Theorem 2.4 that it is a 2-approximation.

  1. Start with S empty.
  2. Compute a maximal matching M in the graph: a set of pairwise disjoint edges to which no further edge can be added.
  3. For each edge in M, add both of its endpoints to S.
  4. Output S.

Why it works, in two steps. First, S is a valid cover: if some edge had neither endpoint in S, it could have been added to M, contradicting maximality. Second, the matching edges share no vertices, so any cover, including an optimal one, needs at least one distinct endpoint for each edge of M, hence OPT ≥ |M|. The algorithm returns |S| = 2|M| ≤ 2 · OPT vertices.

The arithmetic on a four-vertex path

This small case is an illustration built for this page, not an example from either source. Take a path with vertices a, b, c, d and edges ab, bc, cd. The set {b, c} touches all three edges, and no single vertex does, so OPT = 2.

  • If the maximal matching chosen is {ab, cd}, the algorithm outputs S = {a, b, c, d}, size 4. Ratio 4/2 = 2. The bound is met exactly, so the factor of 2 cannot be improved by a sharper analysis of this algorithm.
  • If the maximal matching chosen is {bc}, no further edge can be added, so the matching is maximal. The algorithm outputs S = {b, c}, size 2, which is optimal.

The same algorithm, run on the same graph, gives either the worst allowed answer or the optimum depending on an arbitrary choice. That is typical: the guarantee describes the worst case over inputs and over the algorithm’s free choices, not the typical result.

Other routes to the same ratio

The Cornell notes treat the weighted version, where each vertex has a cost. They obtain a 2-approximation by linear-programming rounding: solve the relaxation in which each vertex variable x_v lies between 0 and 1, then include every vertex with x_v ≥ 1/2. The same notes also give a primal-dual algorithm for weighted vertex cover. Reaching a ratio of 2 by three different techniques is a reminder that the technique and the ratio are separate things; if you work with integer programs in research, the CASRAI guide to mixed integer programming covers the exact-solver side of the same trade-off.

Worked example 2: greedy set cover

In set cover, a universe of n elements and a family of subsets are given, and the goal is to pick the fewest subsets whose union is the whole universe. Chekuri’s notes show that the greedy algorithm, which repeatedly picks the set covering the most still-uncovered elements, is a (ln n + 1)-approximation. The ratio grows with the instance size, an instance of the α(|I|) dependence described above.

The Cornell notes treat the weighted version. At each step the algorithm picks the set S_k that minimises w_k / |T ∩ S_k|, where w_k is the set’s weight and T is the set of elements not yet covered; in words, the cheapest price per newly covered element. The notes bound its ratio by 1 + ln(max |S_i|), where the maximum is over the sizes of the given sets.

A tiny illustration, again constructed for this page: universe {1, 2, 3, 4, 5, 6} with sets A = {1, 2, 3, 4}, B = {5, 6}, C = {1, 2, 5} and D = {3, 4, 6}. Greedy first picks A (it covers four new elements). The uncovered elements are then {5, 6}, and B covers both, so greedy returns {A, B}, two sets. Two sets are also optimal here, since no single set covers all six elements. Greedy is not always this lucky, and the logarithmic guarantee is what holds in general.

Hardness limits: what no approximation algorithm can do

A ratio is only informative next to the best ratio that is provably possible. Both sources report such limits, and they are a different kind of result: they say that a better ratio would imply something believed to be false, usually P = NP.

  • Set cover. Chekuri’s notes cite Feige’s theorem: unless NP is contained in DTIME(n^O(log log n)), no polynomial-time algorithm achieves a (1 − o(1)) ln n approximation. The notes state that the hardness has been strengthened to hold under the assumption P ≠ NP. Greedy’s ln n + 1 is therefore close to the best possible.
  • Maximum coverage. Unless P = NP, there is no (1 − 1/e − ε)-approximation for any fixed ε above zero, according to the same notes.
  • Vertex cover. The notes record that the best known ratio is 2 − Θ(1/√log n), that unless P = NP no ratio below 1.36 is possible, and that under the Unique Games Conjecture no (2 − ε)-approximation exists. For planar graphs the situation changes completely: Baker’s technique gives a polynomial-time approximation scheme.
  • k-center. The notes list a 2-approximation together with a proof that no (2 − ε)-approximation exists, so for that problem the simple algorithm is already optimal.

The data table below the guide collects these problem, algorithm and bound pairs in one place, with the source for each.

Other techniques the sources cover

The Cornell notes present a randomised algorithm for Max-Cut with ratio 2 (a random assignment of vertices to the two sides, analysed in expectation), and then a stronger algorithm that rounds a semidefinite-programming relaxation to reach a ratio of about 0.878 in the maximisation convention, which is about 1.14 in the other. Randomisation is a recurring tool in this area; the CASRAI guide to randomized algorithms explains the underlying ideas and how expected-value guarantees differ from guarantees that hold on every run.

Chekuri’s notes also give a table of contents of further results, including a polynomial-time approximation scheme (PTAS) for multiprocessor scheduling and an asymptotic PTAS for bin packing. A PTAS is a family of algorithms that gets within 1 + ε of the optimum for any fixed ε above zero, with running time polynomial for each fixed ε. It is the strongest kind of approximation result short of an exact algorithm.

How to implement, test and report an approximation algorithm

No software package is required to apply these ideas; the algorithms above are short enough to implement directly in any language. A practical workflow follows from how the guarantees are built.

  1. State the problem and the objective direction. Minimisation or maximisation decides which inequality you are proving or quoting.
  2. Write the guarantee as an inequality between ALG and OPT before you quote a ratio, so readers of your methods section cannot confuse the two conventions in the table above.
  3. Locate the lower bound on OPT that the proof uses. In the vertex cover example it is the size of the matching; in LP rounding it is the value of the relaxation. Implementing that bound lets you compute a certificate on each instance you run.
  4. Test on small instances where OPT is known, as with the four-vertex path above, and check that the output never violates the stated bound. A violation means an implementation error or a misread guarantee.
  5. Report the guarantee and the measurements separately. The worst-case ratio is a property of the algorithm. A ratio measured on benchmark instances is evidence about those instances only. For methods of presenting results across many instances and solvers, see the CASRAI guide to performance profiles.

Common reading mistakes

  • Treating a worst-case ratio as the expected quality. The ratio bounds the worst instance; the algorithm may do far better on instances you care about, as the second matching in the path example shows.
  • Comparing ratios written under different conventions. Normalise to an ALG versus OPT inequality first.
  • Ignoring the dependence on instance size. A ratio such as ln n + 1 grows with n; quoting it as a constant hides this.
  • Quoting hardness without its assumption. Some bounds hold under P ≠ NP, others only under stronger conjectures such as the Unique Games Conjecture; name the assumption when you cite the bound.
  • Assuming a ratio carries over to a variant. The unweighted, weighted and planar versions of vertex cover have different best-known results.

Frequently asked questions

What is an approximation algorithm?

It is a polynomial-time algorithm for an optimisation problem, usually an NP-hard one, that returns a feasible solution guaranteed to be within a stated factor of the optimum on every instance. The factor is its approximation ratio.

What is the approximation ratio?

It is the worst-case multiplicative gap between the algorithm’s solution value and the optimal value, taken over all instances. A ratio of 2 for minimisation means the output is never more than twice the optimum.

Why can an approximation ratio be written both as 2 and as 1/2?

Different sources adopt different conventions for maximisation problems. One writes the ratio as a number at most 1 (output at least α times the optimum); the other writes it as a number at least 1 (the optimum is at most α times the output). Convert both to an inequality between the algorithm’s value and OPT to compare them.

Is the matching-based vertex cover algorithm the best possible?

It achieves a ratio of 2. According to Chekuri’s notes, the best known ratio is slightly better, 2 − Θ(1/√log n), but no ratio below 1.36 is possible unless P = NP, and none below 2 − ε is possible under the Unique Games Conjecture.

Can greedy set cover be improved?

Not substantially. Greedy achieves ln n + 1, and Feige’s theorem, as presented in the same notes, shows that a (1 − o(1)) ln n approximation is not possible in polynomial time under the standard assumptions cited there.

What is a PTAS?

A polynomial-time approximation scheme is a family of algorithms that, for any fixed ε above zero, returns a solution within a factor 1 + ε of the optimum in time polynomial in the input size. Vertex cover on planar graphs has one (Baker), whereas general vertex cover does not unless P = NP.

Sources

Data: Approximation guarantees and hardness bounds for classic optimisation problems

Compiled from two university lecture-note sets on approximation algorithms (UIUC CS583 and Cornell CS 6820). Each row pairs a problem with an algorithm, its proven guarantee and the stated limit on what any polynomial-time algorithm can achieve.

Period covered: 2016/2021.

Approximation guarantees and hardness bounds for classic optimisation problems
ProblemObjectiveAlgorithmProven guaranteeStated limit on any polynomial-time algorithmSource
Vertex coverMinimiseMaximal matching, take both endpoints2-approximationNo ratio below 1.36 unless P = NP; no 2 - epsilon under the Unique Games ConjectureUIUC CS583
Weighted vertex coverMinimiseLP relaxation rounding (include vertices with x_v at least 1/2)2-approximationSame limits as vertex coverCornell CS 6820
Set coverMinimiseGreedy (most uncovered elements per step)ln n + 1No (1 - o(1)) ln n approximation (Feige); holds under P != NPUIUC CS583
Weighted set coverMinimiseGreedy (minimum weight per newly covered element)1 + ln(max set size)Not stated in the note set for this rowCornell CS 6820
Maximum coverageMaximiseNot stated in the note set for this rowNot stated in the note set for this rowNo (1 - 1/e - epsilon) approximation unless P = NPUIUC CS583
Max-CutMaximiseRandomised assignment of vertices to sidesRatio 2 (expected value, second convention)Not stated in the note set for this rowCornell CS 6820
Max-CutMaximiseSemidefinite programming relaxation with roundingAbout 0.878 (about 1.14 in the second convention)Not stated in the note set for this rowCornell CS 6820
k-centerMinimiseNot stated in the note set for this row2-approximationNo (2 - epsilon) approximationUIUC CS583

Sources

Compiled by CASRAI from the sources above. Free to reuse under CC BY 4.0 with attribution.

Follow CASRAI

Research-administration guidance, standards updates and independent tool reviews.

Ask CASRAI · free to try

Ask about Approximation Algorithms: Ratios, Worked Examples, Hardness Limits

2 free questions a day, no account.

An AI assistant for research: funder rules, compliance, methods and publishing. It links the sources behind its answers and labels answers that come from a web search.

Answers draw on CASRAI's guides and dictionary plus the federal and funder documents we index: Federal Register, Grants.gov, Regulations.gov and UKRI.

Works on this site and inside Claude, Cursor and the AI tools you already use.

Everything CASRAI publishes — this page, the dictionary, the guides and the news — stays open to read, with no account and no card.

Referenced across the research world

University of Cambridge logoColumbia University logoCrossref logoUniversity of Edinburgh logoHarvard University logoUniversity of Oxford logoPrinceton University logoStanford School of Medicine logoUniversity College London logoORCID logoUniversity of Cambridge logoColumbia University logoCrossref logoUniversity of Edinburgh logoHarvard University logoUniversity of Oxford logoPrinceton University logoStanford School of Medicine logoUniversity College London logoORCID logo
  • University of Cambridge logo
  • Columbia University logo
  • Crossref logo
  • University of Edinburgh logo
  • Harvard University logo
  • University of Oxford logo
  • Princeton University logo
  • Stanford School of Medicine logo
  • University College London logo
  • ORCID logo

View CASRAI adoption →