Approximation Algorithms

An approximate algorithm is a way of dealing with NP—completeness for optimization problem. This technique does not guarantee the best solution. The goal of an approximation algorithm is to come as close as possible to the optimum value in a reasonable amount of time which is at most polynomial time. If we are dealing with optimization problem {maximization or minimization}
with feasible solution having positive cost then it is worthy to look at approximate algorithm for near optimal solution.

Vertex Cover Problem

A vertex cover of an undirected graph G =(V.E) is a subset V‘ I V such that for all edges (u.v) EE either usV’ or vsV’ or u and v 2 V’. The problem here is to ﬁnd the vertex cover of minimum size in a given graph G. Optimal vertex—cover is the optimization version of an NP—complete problem but it is not too hard to find a vertex-cover that is near optimal.

Algorithm

ApproxVertexCover {G}
{
C ={ } ;
E’ = E
while E' is not empty
do Let (u, v} be an arbitrary edge of E‘
C = C U {u, v}
Remove from E' every edge incident on either u or v
return C
}

Example: (vertex cover running example for graph below)

Analysis:

If E' is represented using the adjacency lists the above algorithm takes O (V+E) since each edge is processed only once and every vertex is processed only once throughout the whole operation.