Design and Analysis of Algorithms (DAA)

Approximation Algorithms

30 mins

Understand how to solve intractable optimization problems by trading exact optimality for guaranteed speed using Approximation Algorithms, focusing on the Vertex Cover problem.

Learning Goals

Define Approximation Algorithms and the Approximation Ratio.
Explain why Approximation Algorithms are critical for solving NP-Hard optimization problems.
Trace the 2-Approximation Algorithm for the Vertex Cover problem.

Why Approximation Algorithms?

In previous modules, we learned that NP-Hard optimization problems (like the Traveling Salesperson Problem, Bin Packing, or Vertex Cover) have no known polynomial-time algorithms. If we want the exact optimal answer, we are forced to use algorithms like Backtracking or Branch & Bound, which take exponential time ( $O(2^n)$ ) and crash on large datasets.

Approximation Algorithms are the engineering compromise. Instead of spending centuries looking for the perfect answer, they guarantee a "near-optimal" answer in fast, polynomial time.

The Approximation Ratio ( $\rho$ )

We measure how "near-optimal" the algorithm is using the Approximation Ratio ( $\rho$ ). For a minimization problem (like finding the smallest vertex cover), the ratio is: $\rho = \frac{\text{Cost of Approximation Algorithm}}{\text{Cost of True Optimal Solution}}$

If an algorithm has a ratio of 2, it is called a "2-Approximation Algorithm." This mathematically guarantees that the answer it gives will never be more than twice the size of the true optimal answer, no matter the input.

Trace: 2-Approximation Algorithm for Vertex Cover

1
Step 1
The Vertex Cover problem asks us to find the minimum number of vertices that touch every single edge in a graph. Finding the true minimum is NP-Hard. We will trace a greedy 2-Approximation algorithm that runs in $O(V+E)$ time.
2
Step 2
Optimal Vertex Cover: Nodes {B, E} (Size = 2). They touch all 5 edges.
3
Step 3
Initialize an empty set $C$ for the cover.

While there are edges left in the graph:

Pick any arbitrary edge $(u, v)$ .

Add BOTH endpoints $u$ and $v$ to the cover $C$ .

Remove every edge from the graph that touches $u$ or $v$ .

Return $C$ .
4
Step 4
Let's randomly pick edge (C, E). We add both C and E to our cover: $C = \{C, E\}$ . We now delete edge (C,E), and all other edges touching C or E. This deletes (B,C) and (B,D). Wait, D is connected to E! It deletes (C,E), (B,C), and (D,E).
5
Step 5
The only edge surviving in the graph is (A, B). We pick edge (A, B). We add both A and B to our cover: $C = \{C, E, A, B\}$ . We delete edge (A,B). The graph now has 0 edges left.
6
Step 6
Our greedy algorithm returned a cover of size 4 (nodes C, E, A, B). The true optimal cover was size 2 (nodes B, E). Notice that our answer ( $4$ ) is exactly $2 \times$ the optimal ( $2$ ). Because we add both endpoints of an edge every time, the worst we can ever do is exactly double the optimal answer. This mathematically proves it is a 2-Approximation Algorithm!

Knowledge Check

Question 1 of 2

Q1Single choice

Why are Approximation Algorithms important in the context of NP-hard problems?

Because they find the exact optimal solution faster than Branch and Bound.

Because they guarantee a near-optimal solution in polynomial time when exact algorithms would take exponential time.

Because they convert NP-Hard problems into Class P problems.

Because they always find the optimal solution by making random choices.

PYQ Analysis & Exam Preparation — Module 4

Randomized Algorithms