19.14 Approximation Ratios

Some optimization problems are easy to state and hard to solve exactly. We may want the smallest set of servers that covers all regions, the cheapest route visiting every city, the best subset of ads under a budget, or the minimum number of machines needed to schedule jobs. For many such problems, exact algorithms are too expensive for large inputs.

Approximation algorithms address this situation directly. Instead of requiring the optimal solution, they produce a solution that is provably close to optimal. The approximation ratio is the formal measure of “close.”

This section introduces approximation ratios and shows how to reason about algorithms that trade exact optimality for speed and scalability.

Problem

Suppose you need to solve an optimization problem.

There is an optimal solution:

OPT

but computing it exactly is too expensive.

Your algorithm returns:

ALG

You want to know how good ALG is compared with OPT.

For a minimization problem, such as minimum vertex cover, smaller is better.

For a maximization problem, such as maximum coverage, larger is better.

Approximation ratios provide a uniform way to compare these values.

Solution

For a minimization problem, an algorithm is an α-approximation if:

ALG ≤ α · OPT

where:

α ≥ 1

Example:

ALG ≤ 2 · OPT

means the algorithm returns a solution whose cost is at most twice the optimal cost.

For a maximization problem, an algorithm is often described as an α-approximation if:

ALG ≥ α · OPT

where:

0 < α ≤ 1

Example:

ALG ≥ 0.9 · OPT

means the algorithm returns a value at least 90% of optimal.

Different books sometimes invert the convention for maximization problems and report ratios greater than 1. Always state the convention explicitly.

Minimization Example

Suppose the optimal cost is:

OPT = 100

A 2-approximation guarantees:

ALG ≤ 200

The algorithm may return:

or:

It may not return:

if the guarantee holds.

The ratio is a worst-case guarantee, not an average-case observation.

Maximization Example

Suppose the optimal value is:

OPT = 1000

A 0.8-approximation guarantees:

ALG ≥ 800

The algorithm may return:

or:

It may not return:

if the guarantee holds.

Why Ratios Matter

Runtime alone is insufficient.

Consider two algorithms for the same minimization problem:

Algorithm	Runtime	Output Cost
Exact	O(2ⁿ)	OPT
Approximate	O(n²)	≤ 2OPT

The exact algorithm may be unusable for large n.

The approximation algorithm gives a weaker answer but finishes quickly.

The ratio tells you precisely how much quality you may lose.

Recipe: Proving an Approximation Ratio

Most approximation proofs follow this structure.

First, define a lower or upper bound on the optimal solution.

For minimization:

lower_bound ≤ OPT

For maximization:

upper_bound ≥ OPT

Then show your algorithm’s output is close to that bound.

For minimization:

ALG ≤ α · lower_bound

Since:

lower_bound ≤ OPT

it follows that:

ALG ≤ α · OPT

For maximization:

ALG ≥ α · upper_bound

Since:

upper_bound ≥ OPT

it follows that:

ALG ≥ α · OPT

The proof rarely compares directly to the true optimum, because the optimum is usually hard to compute. It compares to a bound that is easy to reason about.

Example: Vertex Cover

A vertex cover in an undirected graph is a set of vertices touching every edge.

Given edges:

(A, B)
(B, C)
(C, D)

One vertex cover is:

{B, C}

because every edge has at least one endpoint in the set.

The minimum vertex cover problem asks for the smallest such set.

Exact minimum vertex cover is computationally hard in general graphs.

However, there is a simple 2-approximation.

Recipe: Greedy Matching-Based Vertex Cover

Algorithm:

Start with an empty cover.
While uncovered edges remain:
- Pick any uncovered edge (u, v).
- Add both u and v to the cover.
- Remove all edges touched by u or v.
Return the cover.

from collections.abc import Iterable

Edge = tuple[str, str]

def approximate_vertex_cover(edges: Iterable[Edge]) -> set[str]:
    uncovered = set(edges)
    cover: set[str] = set()

    while uncovered:
        u, v = next(iter(uncovered))

        cover.add(u)
        cover.add(v)

        uncovered = {
            (a, b)
            for (a, b) in uncovered
            if a != u and a != v and b != u and b != v
        }

    return cover

Example:

edges = [
    ("A", "B"),
    ("B", "C"),
    ("C", "D"),
]

print(approximate_vertex_cover(edges))

Possible output:

{'A', 'B', 'C', 'D'}

This output is larger than optimal for this small graph, but it is still within the 2-approximation guarantee.

Proof of the 2-Approximation

The algorithm selects a set of edges no two of which share endpoints. This set is a matching.

Call the selected matching:

Every vertex cover must include at least one endpoint from each edge in M.

Because edges in M are disjoint, these requirements do not overlap.

Therefore:

OPT ≥ |M|

The algorithm adds both endpoints of each selected edge, so:

ALG = 2|M|

Combining:

ALG = 2|M| ≤ 2OPT

Therefore the algorithm is a 2-approximation.

This is the standard shape of an approximation proof: find a structural lower bound, then compare the algorithm against it.

Tightness

An approximation bound may be pessimistic, but sometimes it is tight.

For the matching-based vertex cover algorithm, consider a graph made of disjoint edges:

(A1, B1), (A2, B2), ..., (Ak, Bk)

The algorithm selects both endpoints of every edge:

ALG = 2k

An optimal cover selects one endpoint from each edge:

OPT = k

Ratio:

ALG / OPT = 2

The 2 bound cannot be improved for this algorithm by analysis alone.

Additive vs Multiplicative Error

Approximation ratios are multiplicative.

Example:

ALG ≤ 2OPT

An additive guarantee has the form:

ALG ≤ OPT + c

or:

ALG ≥ OPT - c

Additive guarantees are useful when the scale of the optimum is known. Multiplicative guarantees are more common in approximation algorithms because they scale with instance size.

Example:

OPT = 10
ALG ≤ OPT + 5

is meaningful.

But if:

OPT = 10,000,000

then an additive error of 5 is extremely strong and often unrealistic.

Approximation Schemes

Some problems admit approximation schemes.

A polynomial-time approximation scheme, or PTAS, takes an accuracy parameter:

ε > 0

and returns a solution close to optimal.

For a minimization problem:

ALG ≤ (1 + ε)OPT

For a maximization problem:

ALG ≥ (1 - ε)OPT

The runtime is polynomial in input size for fixed ε, but may grow quickly as ε becomes small.

A fully polynomial-time approximation scheme, or FPTAS, is stronger: runtime is polynomial in both input size and 1/ε.

Example: Approximate Knapsack

The 0/1 knapsack problem asks for the most valuable subset of items fitting within a capacity.

Exact dynamic programming can depend on numeric values or capacities.

Approximation schemes scale and round item values to reduce the state space.

The trade-off is explicit:

Smaller ε
Better solution
More computation

Larger ε
Faster computation
Weaker solution

This is a common pattern in approximation algorithms.

Approximation vs Heuristics

A heuristic is an algorithm that often works well but has no formal quality guarantee.

An approximation algorithm includes a proof.

Example:

Method	Guarantee
Greedy heuristic	Usually good in practice
2-approximation	Always within factor 2
PTAS	Within chosen ε
Exact algorithm	Optimal

Heuristics may be useful. Approximation algorithms provide stronger engineering contracts.

Approximation vs Randomization

Approximation and randomization are independent ideas.

An algorithm may be:

Type	Example
Deterministic approximation	Greedy vertex cover
Randomized approximation	Randomized rounding
Exact randomized	Randomized quicksort
Exact deterministic	Merge sort

This chapter studies them together because both techniques trade strict guarantees for practical scalability. But the guarantees differ: randomized algorithms usually bound probability; approximation algorithms bound solution quality.

Common Applications

Approximation ratios appear in:

Scheduling
Facility location
Set cover
Vertex cover
Clustering
Routing
Network design
Resource allocation
Packing and covering
Machine learning optimization

Many of these problems are computationally difficult to solve exactly at scale.

Complexity

The complexity of an approximation algorithm is described by two quantities:

Quantity	Meaning
Runtime	How fast it runs
Approximation ratio	How close it gets

A useful algorithm needs both.

Example:

Runtime: O(n log n)
Ratio: 2

This is a complete performance contract.

Common Mistakes

Do not report empirical quality as an approximation ratio. A ratio requires proof.

Do not compare a minimization algorithm using a maximization convention.

Do not assume a 2-approximation always returns a result twice as large as optimal. It guarantees at most twice optimal.

Do not confuse approximation error with probability of error. Approximation algorithms may be deterministic.

Do not ignore input assumptions. Many ratios hold only for specific problem variants.

Takeaway

An approximation ratio is a worst-case guarantee on solution quality. For minimization, it usually bounds how much larger the algorithm’s cost can be than optimal. For maximization, it bounds how much value the algorithm preserves. The proof usually compares the algorithm to an easy bound on the optimum rather than to the unknown optimum itself. This gives a precise way to trade exactness for speed.