Advanced Topics8 min read

Approximation Algorithms

90% of the way there in 1% of the time — with a proof to back it up
vertex cover:2-approximation, \(O(V+E)\)metric TSP:1.5-approximation (Christofides)set cover:\(O(\log n)\)-approximation (greedy)

Some problems are so hard that finding the exact optimal solution would take longer than the age of the universe — even on the fastest computer. These are the NP-hard problems. So what do you do?

You don't give up. You use an approximation algorithm: a fast algorithm that comes with a provable promise that its answer is never too far from optimal. Not a guess — a mathematical guarantee.

The approximation ratio

An algorithm has approximation ratio α if it always returns a solution within factor α of optimal:

• For minimization: algorithm's answer ≤ α × OPT (α ≥ 1).
• For maximization: algorithm's answer ≥ OPT / α (α ≥ 1).

A ratio of 2 means you're at most twice the optimal cost. A ratio of 1.5 means you're at most 50% above optimal. The closer to 1, the better.

Vertex Cover — the elegant 2-approximation

A vertex cover is a set of vertices S such that every edge has at least one endpoint in S. (Think: placing guards at intersections so every road is watched.) Finding the minimum vertex cover is NP-hard.

The 2-approximation: repeatedly pick any uncovered edge (u, v), add both u and v to the cover, remove all edges incident to either. Repeat until no edges remain. Done in \(O(V+E)\).

Why is this at most 2× optimal? The edges we pick form a matching — no two share a vertex. Our cover takes 2 vertices per selected edge. Any valid cover must include at least 1 vertex per selected edge (to cover it). So |OUR COVER| ≤ 2 × |OPT|.

Metric TSP — Christofides 1.5-approximation

The Traveling Salesman Problem on metric distances (triangle inequality: no shortcut is longer than the path through a third city) admits a beautiful 1.5-approximation:

1. Find a minimum spanning tree T of all cities.
2. Identify the set O of vertices with odd degree in T (always an even count by the handshaking lemma).
3. Find a minimum weight perfect matching M on those odd-degree vertices.
4. Combine T and M into an Eulerian multigraph (every vertex now has even degree).
5. Find an Euler circuit, then shortcut repeated cities (triangle inequality guarantees shortcuts never increase cost).

The result is a tour of cost at most 1.5 × OPT.

Set Cover — the greedy \(O(\log n)\)-approximation

Given a universe of n elements and a collection of sets, find the fewest sets that cover everything. Greedy: always pick the set that covers the most currently uncovered elements. Repeat until everything is covered.

This achieves approximation ratio H_n = 1 + 1/2 + 1/3 + … + 1/n ≈ ln(n). And here's the kicker: no polynomial-time algorithm can do better (unless P=NP). The greedy algorithm is essentially optimal among all efficient algorithms.

PTAS and FPTAS

A Polynomial-Time Approximation Scheme (PTAS) gives you a (1+ε)-approximation for any ε you choose — closer to optimal for smaller ε, but potentially slower. A Fully Polynomial-Time Approximation Scheme (FPTAS) must run in time polynomial in both n and 1/ε — making even tiny ε practical. The 0/1 Knapsack problem has an FPTAS: scale and round item values, then run exact DP, giving a (1+ε)-approximation in \(O(n^2/ε)\) time.

Note: An approximation ratio is a worst-case guarantee — not an average. An algorithm with ratio 2 might return the exact optimal answer on most inputs, but you're covered even on the toughest cases.

Greedy Vertex Cover — 2-Approximation

def vertex_cover_2approx(n, edges):
    """Returns a vertex cover guaranteed to be at most 2x optimal."""
    covered = set()
    cover = set()
    for u, v in edges:
        if u not in covered and v not in covered:
            cover.add(u)
            cover.add(v)
            covered.add(u)
            covered.add(v)
    return cover


# Example: path graph 0-1-2-3
edges = [(0,1), (1,2), (2,3)]
cover = vertex_cover_2approx(4, edges)
print("Cover:", cover)         # e.g. {0, 1, 2, 3} or subset
print("Cover size:", len(cover))  # at most 2 * OPT


# Verify: every edge has at least one endpoint in cover
assert all(u in cover or v in cover for u,v in edges)
print("Valid cover: True")
Output
Cover: {0, 1, 2, 3}
Cover size: 4
Valid cover: True

Complexity

🛡️ Vertex Cover (greedy 2-approx)The ratio of 2 is essentially tight under the Unique Games Conjecture — you likely can't do better efficiently
At most 2× optimal, guaranteed\(O(V + E)\)
✈️ Metric TSP (Christofides)Bottleneck is minimum weight perfect matching; a (1.5−ε) improvement was found in 2020 but Christofides remains the practical standard
At most 1.5× optimal, guaranteed\(O(n^3)\)
🗂️ Set Cover (greedy)m = number of sets; this ratio is optimal under P≠NP — you cannot do better efficiently
At most ln(n) × optimal\(O(n · m)\)
🎛️ Knapsack FPTASTrade accuracy for speed: set ε=0.01 for 1% error; polynomial in both n and 1/ε
At most (1+ε) × optimal\(O(n^2 / ε)\)

Quick check

An approximation algorithm has ratio 3 for a minimization problem. What does this actually guarantee?

Continue reading

NP, NP-Complete, NP-Hard
The million-dollar question: can finding an answer ever be as easy as checking one?
→
Greedy Pattern
Always grab the biggest slice of pizza — sometimes that's optimal, sometimes it isn't
→