Approximation Algorithms

In an optimization problem, we seek the best solution among a collection of possible solutions

When an optimization problem is NP-hard, no polynomial time algorithm exists unless $\text{P}=\text{NP}$

In these situations, an alternative is an approximation algorithm designed to find an approximately optimal solution in polynomial time

Recall the $VERTEX$-$COVER$ problem, shown here

The optimization version of this problem, $MIN$-$VERTEX$-$COVER$, aims to produce one of the smallest vertex covers among all possible covers

We can give a polynomial time algorithm that produces a vertex cover no more than twice the size of an optimal cover

$A=$ “On input $⟨G⟩$, where $G$ is an undirected graph:

1. Mark an edge in $G$ untouched by any marked edge and repeat this stage
2. Otherwise output all nodes that are endpoints of marked edges”

Let $X$ be the set of nodes outputted, and $H$ be the set of edges marked

$X$ is twice as large as $H$, and $H$ is no larger than a smallest vertex cover $Y$, since each edge in $H$ must be touched by a unique node in $Y$, so $A$ works as claimed

$MIN$-$VERTEX$-$COVER$ is an example of a minimization problem

There are also maximization problems

An approximation algorithm is k-optimal if, for a minimization problem, it always finds a solution no more than $k$ times optimal, and for a maximization problem, it always finds a solution at least $\frac{1}{k}$ times optimal

I.e. $A$ is 2-optimal

The $MAX$-$CUT$ problem asks for a largest cut (a separation of vertices with the most cut edges) in a graph $G$

While this problem is NP-complete, as before we are able to approximate the problem within a factor of 2 with a simple algorithm

$B=$ “On input $⟨G⟩$, where $G$ is an undirected graph with nodes $V$:

1. Let $S=\varnothing$ and $T=V$
2. If moving a single node increases the size of the cut, make that move and repeat this stage
3. Otherwise output the current cut and halt”

This algorithm makes small local improvements

$B$ is at least half optimal, because at every individual node the number of cut edges must be at least as large as the number of uncut edges, or else that node would be shifted to the other side