Neural Sync Active

Approximation Algorithms

Registry Synced

Approximation Algorithms

628 words

3 min read

Reading compass

Now · 🎯 Learning Objectives

Approximation Algorithms

🎯 Learning Objectives

Define approximation ratio and compare to optimal
Design 2-approximation for vertex cover using maximal matching
Explain the traveling salesman problem approximations
Analyze set cover using greedy log(n) approximation

1. Introduction

1.1 Intuition

For NP-hard optimization problems, we can't find optimal solutions efficiently. Approximation algorithms find provably good solutions in polynomial time, with a guarantee on how close they are to optimal.

1.2 Approximation Ratio

An algorithm has approximation ratio $\rho$ if for all inputs:

\frac{C}{C^*} \leq \rho \text{ (for minimization)}

Where

C

is the algorithm's cost and

C^*

is the optimal cost.

2. Vertex Cover

2.1 Problem

Find the smallest set of vertices that touches every edge.

2.2 2-Approximation via Maximal Matching


python
def vertex_cover_approx(G):
    C = set()
    E_uncovered = set(G.edges)
    while E_uncovered:
        (u, v) = E_uncovered.pop()
        C.add(u)
        C.add(v)
        # Remove all edges incident to u or v
        for e in list(E_uncovered):
            if u in e or v in e:
                E_uncovered.remove(e)
    return C

Theorem: This gives a 2-approximation. The edges picked form a matching, and any vertex cover must include at least one endpoint of each matched edge → |C| ≤ 2|OPT|.

3. Traveling Salesman Problem (TSP)

3.1 Metric TSP (Triangle Inequality)

Algorithm (2-approximation):

Compute MST of the graph
Double each edge (Eulerian graph)
Find Eulerian tour
Take shortcuts to get Hamiltonian cycle Christofides Algorithm (1.5-approximation):
Compute MST
Add minimum-weight perfect matching on odd-degree vertices
Find Eulerian tour
Take shortcuts

4. Set Cover

4.1 Greedy Algorithm


python
def set_cover(U, sets):
    covered = set()
    cover = []
    while covered != U:
        # Pick set covering most uncovered elements
        best_set = max(sets, key=lambda s: len(s - covered))
        cover.append(best_set)
        covered |= best_set
    return cover

Theorem: Greedy set cover is a

\ln(n)

-approximation, where

n = |U|

. No better polynomial-time algorithm exists unless P = NP.

5. 📝 Practice Questions

Q1: What is the approximation ratio of the maximal matching algorithm for vertex cover?

Answer: 2-approximation. The algorithm picks both endpoints of each matched edge. Since the edges form a matching, any vertex cover must include at least one endpoint per edge. Thus |C_alg| = 2|M| and |OPT| ≥ |M|, giving |C_alg| ≤ 2|OPT|. Q2: Why does the TSP 2-approximation require the triangle inequality?

Answer: Shortcutting in the Eulerian tour uses the triangle inequality (cost of direct edge ≤ cost of path) to ensure the shortcut doesn't increase cost. Without it, the shortcut could be arbitrarily expensive, breaking the approximation guarantee. Q3: What is the greedy set cover approximation ratio?

Answer: H(n) ≈ ln(n) + O(1), where n is the number of elements. This is essentially optimal — no polynomial-time algorithm achieves a better ratio unless P = NP. Q4: Give an example where the greedy vertex cover (always pick highest-degree vertex) is worse than the maximal matching approach.

Answer: A star graph: greedy picks the center (optimal, good). But consider a graph where high-degree vertices are mostly covered by many smaller-degree vertices' edges. The maximal matching approach guarantees 2-approximation regardless. Q5: What is an approximation-preserving reduction?

Answer: A reduction from problem A to problem B such that an α-approximation for B implies a β-approximation for A, where β depends on α. Used to prove inapproximability results.

6. 🔗 Cross-References

Week 6 - NP-Completeness: Approximation helps cope with NP-hardness
Week 8 - Randomized Algorithms: Randomized approximation schemes
BSCS4021 - Week 10 - Parameterized: Alternate approach to hard problems Join Discord PreviousNP-CompletenessNextRandomized Algorithms