Approximation Algorithms, in depth: the lower-bound sandwich, vertex cover, set cover, LP rounding, metric TSP and a knapsack FPTAS

The approximation ratio and the sandwich

For a minimisation problem, an algorithm is a rho-approximation if, for every instance, its cost ALG satisfies ALG ≤ rho · OPT, where OPT is the optimal cost and rho ≥ 1. For maximisation the convention used here is ALG ≥ OPT / rho, though some texts write a ratio below 1 instead, such as 1 − epsilon. The ratio may be a constant like 2, or a function of the input size like ln n.

The difficulty is obvious once stated: you cannot compute OPT, so how can you prove anything relative to it? The answer is the approximation sandwich. Find a quantity LB that you can compute and that provably satisfies LB ≤ OPT, then show ALG ≤ rho · LB. Chaining the inequalities gives ALG ≤ rho · OPT without ever knowing OPT. Every algorithm below is a different choice of LB.

Vertex cover by maximal matching

A vertex cover of a graph is a set of vertices touching every edge. Finding the smallest is NP-hard. The algorithm is almost embarrassingly simple: scan the edges, and whenever an edge has neither endpoint in the cover, add both endpoints.

def vertex_cover_matching(edges):
    cover = set()
    for u, v in edges:
        if u not in cover and v not in cover:
            cover.update((u, v))   # (u, v) joins a maximal matching
    return cover

Why it is a 2-approximation. The edges that triggered an addition share no endpoints, so they form a matching M, and it is maximal because any edge left uncovered would have triggered another addition. Any cover, including the optimal one, must contain at least one endpoint of each edge in M, and since those edges are disjoint, OPT ≥ |M|. The algorithm adds exactly two vertices per matching edge, so ALG = 2|M| ≤ 2 · OPT. Here |M| is the lower bound.

Worked example. On the edges a-b, a-c, a-d, b-e, c-f, d-g, e-f, the scan picks a-b, then c-f, then d-g, and returns {a, b, c, d, f, g}, six vertices. Brute force finds the optimum {a, b, d, f} with four. The ratio on this instance is 1.5, inside the guaranteed 2. The bound is tight in general: on a graph made of n disjoint edges, the algorithm takes 2n vertices where n suffice.

Greedy set cover

In set cover you have a universe of n elements and a family of sets with costs; choose the cheapest family whose union is the universe. Monitoring placement, test-suite minimisation and feature selection all reduce to it. The greedy rule picks, at each step, the set with the lowest cost per newly covered element.

def greedy_set_cover(universe, sets, cost):
    uncovered, chosen = set(universe), []
    while uncovered:
        best = min((n for n in sets if sets[n] & uncovered),
                   key=lambda n: cost[n] / len(sets[n] & uncovered))
        chosen.append(best)
        uncovered -= sets[best]
    return chosen

Why it is an H(n)-approximation. Spread each chosen set's cost evenly over the elements it newly covers, giving each element a price. When the k-th to last element is covered, at least k elements remain uncovered, and the optimal solution covers all of them at total cost OPT, so some set covers them at cost per element at most OPT / k. Greedy picks something at least that cheap, so that element's price is at most OPT / k. Summing over all n elements gives ALG ≤ OPT · (1 + 1/2 + ... + 1/n) = H(n) · OPT, and H(n) ≤ ln n + 1.

Worked example of the gap. Take 14 elements in two rows, R1 = {1..7} and R2 = {8..14}, plus C1 with 8 elements (four from each row), C2 with 4, and C3 = {7, 14}, all at unit cost. The optimum is the two rows. Greedy sees C1 covering 8 against the rows' 7, takes it, then C2 covering 4 against the rows' 3, then C3, and the code prints ['C1', 'C2', 'C3']: three sets instead of two. Stacking more columns of halving size makes the ratio grow like log n, matching the bound.

LP relaxation and rounding

When vertices carry weights, the matching argument breaks, because the cheap endpoint and the expensive one count differently. Linear programming restores a lower bound. Write the integer program with a variable x_v in {0, 1} per vertex, minimise the sum of w_v x_v subject to x_u + x_v ≥ 1 for every edge, then relax it to 0 ≤ x_v ≤ 1. The LP optimum LP* is at most OPT because every integer solution is also a fractional one. Solve it, then round: put v in the cover whenever x_v ≥ 1/2.

Every edge constraint x_u + x_v ≥ 1 forces at least one of the two to be at least 1/2, so the rounded set is a cover. Rounding at most doubles each chosen variable, so ALG ≤ 2 · LP* ≤ 2 · OPT. The ratio OPT / LP* on the worst instance is the integrality gap; for vertex cover it approaches 2 on complete graphs, where x_v = 1/2 everywhere is feasible, so no rounding of this LP can prove better than 2. LP duality gives a faster route to the same bound through a primal-dual algorithm that never calls a solver; see LP Duality and Integer Programming and LP for the machinery.

Metric TSP

The travelling salesman tour visits every city once and returns. When distances obey the triangle inequality, a minimum spanning tree gives a lower bound: deleting one edge from the optimal tour leaves a spanning tree, so MST ≤ OPT. Walk the tree depth-first, which traverses every edge twice for a cost of 2 · MST, then shortcut repeated cities. The triangle inequality means shortcuts never lengthen the walk, so the tour costs at most 2 · OPT.

Christofides' algorithm improves this to 3/2 by adding a minimum-weight perfect matching on the tree's odd-degree vertices instead of doubling every edge; the matching costs at most OPT / 2. In 2020 Karlin, Klein and Oveis Gharan proved a randomised variant beats 3/2 by roughly 10^-36, a theoretical milestone of no practical size. Without the triangle inequality there is no constant-factor approximation at all unless P = NP, because such an algorithm could decide Hamiltonian cycle. This is why checking that your distances are metric, not just plausible, matters before trusting any TSP guarantee.

Approximation schemes: a knapsack FPTAS

Some problems admit a whole family of algorithms that trade running time for accuracy. A PTAS achieves ratio 1 + epsilon for any fixed epsilon in time polynomial in n, possibly exponential in 1/epsilon. An FPTAS is polynomial in both. The 0/1 knapsack problem has an FPTAS built on its pseudo-polynomial dynamic program, covered in Knapsack Problem. Scale every value down by K = epsilon · vmax / n, round down, and run the exact DP indexed by scaled profit, which now has only about n² / epsilon profit levels.

def knapsack_fptas(values, weights, cap, eps):
    n = len(values)
    vmax = max(v for v, w in zip(values, weights) if w <= cap)
    k = eps * vmax / n
    scaled = [int(v // k) for v in values]
    total = sum(scaled)
    best = [0] + [float("inf")] * total      # best[p] = min weight for profit p
    take = [[False] * (total + 1) for _ in range(n)]
    for i in range(n):
        for p in range(total, scaled[i] - 1, -1):
            w = best[p - scaled[i]] + weights[i]
            if w < best[p]:
                best[p], take[i][p] = w, True
    p = max(q for q in range(total + 1) if best[q] <= cap)
    items = []
    for i in range(n - 1, -1, -1):           # walk back through the decisions
        if take[i][p]:
            items.append(i)
            p -= scaled[i]
    return sorted(items)

Rounding loses less than K per item, so at most nK = epsilon · vmax ≤ epsilon · OPT in total, which gives value at least (1 − epsilon) · OPT. With values 62, 75, 89, 41, 58, 97, weights 11, 14, 17, 8, 12, 20 and capacity 40, the exact optimum is items 0, 2 and 4 for value 209. At epsilon = 0.5 the scaled values are 7, 9, 11, 5, 7, 11, coarse enough that the DP picks items 1, 2 and 3 for 205. At epsilon = 0.25 the scaled values are 15, 18, 22, 10, 14, 23, and it finds the optimal 209. Both results satisfy the guarantee; the smaller epsilon simply buys more resolution.

Hardness limits

Hardness of approximation results tell you when a better factor is not worth searching for. They assume P ≠ NP unless noted.

Using approximation in practice

In production, a guarantee is a floor, not a target. The common pattern has three steps. First, run the approximation algorithm to get a valid solution fast. Second, improve it with local search, for example 2-opt moves for tours or removing redundant sets from a cover, which never breaks the guarantee because it only lowers cost. Third, compute the lower bound you already have, matching size or LP value, and report the a posteriori gap ALG / LB for this instance. Real instances often show gaps of a few percent, far better than the worst-case factor, and the measured gap tells you whether paying for an exact solver is worth it. When it is, hand the bound to a branch-and-bound solver as its starting incumbent. Greedy reasoning in general, and when it is exactly optimal rather than approximate, is covered in Greedy Algorithms.

Failure modes

• Violated preconditions. Feeding asymmetric or non-metric distances to an MST-based TSP algorithm silently voids the bound; validate the triangle inequality on a sample.
• Confusing ratio conventions. A '0.5-approximation' for a maximisation problem and a '2-approximation' can mean the same thing; check which form a library documents.
• Floating-point ties. Greedy cost-per-element comparisons with floats can loop or choose sets that cover nothing new; filter on positive coverage, as the code above does.
• Pseudo-polynomial blow-up. The FPTAS table has roughly n² / epsilon columns; epsilon = 0.001 on 10,000 items is far too large in memory.
• Unbounded LP solutions. Rounding assumes the LP solved to optimality; a solver stopped at a time limit gives no valid lower bound.
• Trusting worst case as typical. A 2-approximation may be 1.02 on your data, or a heuristic without a proof may be better; measure.

Trade-offs

What to do next

1. Write down your problem precisely and find the textbook problem it reduces to: cover, packing, tour, cut or scheduling.
2. Check the preconditions of the known algorithm, such as the triangle inequality or non-negative weights.
3. Implement the simplest algorithm with a proven factor and keep the lower bound it computes.
4. Log ALG, LB and the gap ALG / LB for every production instance.
5. Add local search on top, and confirm it only ever reduces cost.
6. Look up the hardness limit before spending time on a better factor.
7. If the measured gap is still too large, run an exact solver seeded with your solution and stop it at a time budget.