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 FPTAS
Trade 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