Approximation algorithms are a cornerstone of algorithmic design when dealing with NP‑hard optimization problems. This tutorial guides software engineers through the theory, design patterns, and practical implementations of approximation algorithms, with code examples in Python, Java, and C++.
1. Introduction to Approximation Algorithms
In many real‑world applications, finding an exact optimal solution is computationally infeasible. Approximation algorithms provide solutions that are "good enough" within provable bounds, often in polynomial time.
1.1 When to Use Approximation Algorithms
- The problem is NP‑hard or NP‑complete.
- Exact solutions are required only for small instances.
- A solution within a known factor of optimal is acceptable.
- Time or resource constraints dominate over absolute optimality.
2. Core Concepts
2.1 Approximation Ratio
For a minimization problem, an algorithm has approximation ratio ρ if for every input I:
ALG(I) ≤ ρ·OPT(I)
For maximization problems the inequality reverses: ALG(I) ≥ (1/ρ)·OPT(I).
2.2 PTAS and FPTAS
A Polynomial‑Time Approximation Scheme (PTAS) yields a (1+ε)-approximation for any ε>0, with running time polynomial in the input size but possibly exponential in 1/ε. A Fully Polynomial‑Time Approximation Scheme (FPTAS) improves this by making the running time polynomial in both input size and 1/ε.
3. Common Design Techniques
- Greedy heuristics
- Local search
- Linear programming relaxation + rounding
- Primal‑dual method
- Dynamic programming with scaling
3.1 Greedy Algorithms
Greedy approaches build a solution step‑by‑step, always choosing the locally optimal option. They are simple to implement and can achieve constant‑factor guarantees for many problems.
Example: Vertex Cover
Given an undirected graph G=(V,E), the greedy algorithm repeatedly picks an arbitrary uncovered edge (u,v) and adds both u and v to the cover.
# Greedy 2‑approximation for Vertex Cover (Python)
def greedy_vertex_cover(graph):
"""graph: dict mapping vertex -> set of neighboring vertices"""
uncovered = set((u, v) for u in graph for v in graph[u] if u < v)
cover = set()
while uncovered:
u, v = uncovered.pop() # pick an arbitrary edge
cover.update([u, v]) # add both endpoints
# remove all edges incident to u or v
uncovered = {e for e in uncovered if u not in e and v not in e}
return cover
"""The returned set is at most twice the size of a minimum vertex cover."""// Greedy Vertex Cover (Java)
import java.util.*;
public class GreedyVertexCover {
public static Set<Integer> solve(Map<Integer, Set<Integer>> graph) {
Set<Pair> edges = new HashSet<>();
for (int u : graph.keySet()) {
for (int v : graph.get(u)) {
if (u < v) edges.add(new Pair(u, v));
}
}
Set<Integer> cover = new HashSet<>();
while (!edges.isEmpty()) {
Pair e = edges.iterator().next();
cover.add(e.u);
cover.add(e.v);
edges.removeIf(p -> p.u == e.u || p.v == e.u || p.u == e.v || p.v == e.v);
}
return cover;
}
private static class Pair { int u, v; Pair(int u, int v){this.u=u;this.v=v;} }
}3.2 Linear Programming Relaxation
Many combinatorial problems can be expressed as integer linear programs (ILP). By relaxing integrality constraints we obtain a fractional solution that can be rounded while preserving approximation guarantees.
Example: Set Cover – LP Rounding
The classic set‑cover problem admits an O(log n)‑approximation via LP rounding. The algorithm solves the LP, then repeatedly picks the set with highest uncovered weight until all elements are covered.
# LP‑based Set Cover (Python, using PuLP)
import pulp
def lp_set_cover(universe, sets):
prob = pulp.LpProblem('SetCover', pulp.LpMinimize)
# decision variable for each set
x = {i: pulp.LpVariable(f'x_{i}', lowBound=0, upBound=1, cat='Continuous')
for i in range(len(sets))}
# objective: minimize total weight (assume weight 1 for simplicity)
prob += pulp.lpSum(x[i] for i in x)
# each element must be covered
for e in universe:
prob += pulp.lpSum(x[i] for i, s in enumerate(sets) if e in s) >= 1
prob.solve()
# simple greedy rounding: pick any set with x_i >= 1/ln|U|
threshold = 1.0 / (len(universe).bit_length())
cover = [i for i in x if pulp.value(x[i]) >= threshold]
return cover
"""The resulting cover is within O(log n) of optimal."""4. Classic Approximation Algorithms
4.1 Knapsack – Fully Polynomial‑Time Approximation Scheme
The 0/1 knapsack problem admits an FPTAS by scaling item values.
// FPTAS for 0/1 Knapsack (C++)
#include <bits/stdc++.h>
using namespace std;
vector<int> knapsackFPTAS(const vector<int>& w, const vector<int>& v, int W, double eps) {
int n = w.size();
int Vmax = *max_element(v.begin(), v.end());
long long K = (long long)ceil(eps * Vmax / n);
// scale values
vector<long long> vScaled(n);
for (int i = 0; i < n; ++i) vScaled[i] = v[i] / K;
long long Vsum = accumulate(vScaled.begin(), vScaled.end(), 0LL);
const long long INF = 1LL << 60;
vector<long long> dp(Vsum + 1, INF);
dp[0] = 0;
for (int i = 0; i < n; ++i) {
for (long long val = Vsum; val >= vScaled[i]; --val) {
dp[val] = min(dp[val], dp[val - vScaled[i]] + w[i]);
}
}
long long best = 0;
for (long long val = 0; val <= Vsum; ++val) {
if (dp[val] <= W) best = val;
}
// reconstruct solution (optional) ...
return {};
}
"""Running time is O(n^3 / eps)."""4.2 Traveling Salesman – Christofides' Algorithm
For metric TSP, Christofides' algorithm achieves a 3/2‑approximation by combining a minimum spanning tree, a minimum‑weight perfect matching on odd‑degree vertices, and shortcutting an Eulerian tour.
5. Practical Implementation Tips
- Use high‑precision data types (e.g.,
doubleorBigDecimal) when rounding fractional solutions. - Profile the LP solver; for large instances consider specialized combinatorial relaxations.
- Cache intermediate results in dynamic‑programming‑based PTAS to avoid recomputation.
- Validate the approximation ratio empirically on benchmark datasets.
6. Summary
7. Frequently Asked Questions
Q: What is the difference between a PTAS and an FPTAS?
A: A PTAS provides a (1+ε)-approximation for any ε>0 with polynomial time in the input size, but the exponent may depend on 1/ε. An FPTAS improves this by ensuring the running time is polynomial in both the input size and 1/ε.
Q: Can approximation algorithms be used for decision problems?
A: Approximation concepts apply to optimization problems. For decision versions, one typically uses approximation to derive a bound and then decides based on that bound.
Q: How do I prove an approximation ratio?
A: Proofs usually involve comparing the algorithm’s solution cost to the optimal cost using structural arguments (e.g., charging schemes, dual fitting, or probabilistic analysis).
8. Quick Quiz
Q. Which of the following algorithms guarantees a 2‑approximation for the Vertex Cover problem?
- A greedy algorithm that repeatedly picks a random vertex
- The algorithm that repeatedly selects an arbitrary uncovered edge and adds both endpoints
- A linear‑programming rounding that picks vertices with fractional value ≥ 0.5
- A dynamic programming exact solver
Answer: The algorithm that repeatedly selects an arbitrary uncovered edge and adds both endpoints
This classic greedy method yields a cover at most twice the optimal size; the other options either lack a guarantee or are exact.
Q. In Christofides' algorithm, which sub‑problem is solved to handle odd‑degree vertices?
- Maximum matching
- Minimum spanning tree
- Minimum‑weight perfect matching
- Shortest path tree
Answer: Minimum‑weight perfect matching
After forming an MST, the set of odd‑degree vertices is matched with a minimum‑weight perfect matching to make the graph Eulerian.