Approximation Algorithms: Getting Provably Close to Optimal for Hard Problems

Why Approximation Is a Reasonable Response to NP-Completeness

As discussed earlier in this series, proving a problem NP-complete provides strong evidence that no polynomial-time algorithm finds the exact optimal solution. Rather than abandoning the problem, an Approximation Algorithm deliberately trades away the guarantee of finding the exact optimal solution in exchange for the guarantee of running in polynomial time, while still providing a mathematical bound on how far from optimal its answer can possibly be.

Defining the Approximation Ratio

An algorithm has an Approximation Ratio of ρ(n) if, for every input of size n, the ratio between the algorithm's solution cost and the true optimal cost never exceeds ρ(n) (for minimization problems), or never falls below 1/ρ(n) (for maximization problems).

For a minimization problem:
C / C* ≤ ρ(n)

where C is the cost of the approximate solution found,
and C* is the cost of the true optimal solution

A ρ(n) = 2 approximation guarantees the algorithm's
solution never costs more than double the true optimum,
no matter what input is given

This guarantee holds for every possible input, not merely on average — a crucial distinction that gives approximation algorithms genuine mathematical teeth, rather than being merely a heuristic that works well "usually."

The Vertex Cover Problem: A 2-Approximation

A Vertex Cover of a graph is a subset of vertices such that every edge has at least one endpoint in the subset. The Minimum Vertex Cover Problem asks for the smallest such subset, and it is NP-complete, discussed earlier in this series regarding NP-completeness.

APPROX-VERTEX-COVER(G):
  C = empty set
  E' = a copy of G.E
  while E' is not empty:
      let (u, v) be an arbitrary edge from E'
      C = C ∪ {u, v}       // add BOTH endpoints
      remove from E' every edge incident on either u or v
  return C

This algorithm is remarkably simple: repeatedly pick any remaining uncovered edge, add both of its endpoints to the cover, and remove every edge that touches either of them, since they are now covered. Repeat until no edges remain.

Proving the 2-Approximation Guarantee

The proof relies on a clever observation about the edges chosen during the algorithm's execution, called a Matching — a set of edges no two of which share an endpoint.

Key observation: the edges (u,v) selected across all
iterations of the while loop form a matching, since
once u and v are added to C, every edge touching
either of them is removed, so no future selected
edge can share an endpoint with a previous one

Since no two selected edges share an endpoint,
any vertex cover — including the optimal one — must
include at least one endpoint from EACH selected edge
(a single vertex cannot cover two non-adjacent edges)

Therefore: |C*| ≥ (number of selected edges)

But the algorithm's cover C has exactly
2 · (number of selected edges) vertices,
since it adds both endpoints each time

Therefore: |C| = 2 · (number of selected edges) ≤ 2 · |C*|

This proves the algorithm's output is never more than twice the size of the true minimum vertex cover, a guaranteed 2-approximation, achieved with a remarkably simple and fast algorithm running in O(V + E) time.

The Traveling Salesman Problem with the Triangle Inequality

The Traveling Salesman Problem (TSP) asks for the shortest possible route that visits every city exactly once and returns to the start. This problem is NP-complete, and in its most general form, cannot be approximated to any constant factor unless P = NP. However, when the edge weights satisfy the Triangle Inequality (the direct distance between two points is never longer than a path through a third point — a natural assumption for real geographic distances), an elegant 2-approximation exists.

APPROX-TSP-TOUR(G, c):
  compute a minimum spanning tree T of G,
  using an algorithm discussed earlier in this series
  (such as Prim's or Kruskal's algorithm)

  perform a depth-first search traversal of T,
  discussed earlier in this series, listing vertices
  in the order they are first visited

  return the tour visiting vertices in this order,
  then returning to the starting vertex

Why This Achieves a 2-Approximation

The proof connects three quantities using a clever argument. First, any TSP tour, if one edge is removed, becomes a Hamiltonian path, which is itself a spanning tree, so the optimal tour's cost is at least the minimum spanning tree's weight: MST ≤ OPT. Second, a full depth-first traversal of the MST, walking every edge exactly twice (once going down, once coming back up), has total cost exactly 2 · MST. Third, using the triangle inequality, "shortcutting" this doubled traversal — skipping over already-visited vertices to go directly to the next unvisited one — can only decrease the total distance, never increase it.

Combining these facts:
Approximate tour cost ≤ 2 · MST ≤ 2 · OPT

This chain of inequalities proves the algorithm's tour never costs more than twice the true optimal tour, another clean 2-approximation, running in time dominated by the minimum spanning tree computation, discussed earlier in this series, typically O(E log V).

Approximation Ratios Are Not All Equally Good

Different NP-hard problems admit dramatically different quality approximations. Some problems have a Polynomial-Time Approximation Scheme (PTAS), allowing an approximation ratio arbitrarily close to 1 (though the running time grows as the ratio approaches 1). Others, like general TSP without the triangle inequality, have been proven to admit no constant-factor approximation at all unless P = NP. Still others sit in between, admitting some fixed approximation ratio but no better, no matter how cleverly the algorithm is designed. Understanding which category a given NP-hard problem falls into is itself an