Approximation
Algorithms
Refer Cormen Book
Chapter 35
NP – Complete Problems
• Many problems of practical significance are NP-complete
• No polynomial time algorithm to find an optimal solution.
• Three ways to get around NP-completeness.
• First, if the actual inputs are small, an algorithm with
exponential running time may be perfectly satisfactory.
• Second, we may be able to isolate important special cases that
we can solve in polynomial time.
• Third, we might come up with approaches to find near-optimal
solutions in polynomial time (either in the worst case or the
expected case).
• In practice, near-optimality is often good enough.
• We call an algorithm that returns near-optimal solutions an
approximation algorithm.
Performance ratios for
approximation algorithms
• approximation ratio
• for any input of size , the cost of the solution produced by the
algorithm is within a factor of of the cost of an optimal solution:
• For a maximization problem,
• the ratio gives the factor by which the cost of an optimal solution is
larger than the cost of the approximate solution.
• For a minimization problem,
• the ratiogives the factor by which the cost of an optimal solution is
smaller than the cost of the approximate solution.
• The approximation ratio of an approximation algorithm is
never less than 1
• An approximation algorithm with a large approximation ratio
may return a solution that is much worse than optimal.
The vertex-cover
problem
The vertex-cover
problem
• The vertex-cover problem is to find a
vertex cover of minimum size in a given
undirected graph. We call such a vertex
cover an optimal vertex cover.
• This problem is the optimization version
of an NP-complete decision problem.
• Even though we don’t know how to find
an optimal vertex cover in a graph G in
polynomial time, we can efficiently find a
vertex cover that is near-optimal.
Explanation • The input graph G,
which has 7 vertices and
8 edges.
• The edge (b,c) shown heavy, is
the first edge chosen by
APPROX-VERTEX-COVER.
• Edges (a,b), (c,e), and (c,d),
shown dashed, are removed
since they are now covered by
some vertex in C.
Explanation
• Edge (e,f) is chosen
• vertices e and f are added to C.
Explanation
• Edge (d,g) is chosen;
• vertices d and g are added to C.
Conclusion
• The set C , which is the • The optimal vertex cover
vertex cover produced by for this problem contains
APPROX-VERTEX-COVER, only three vertices: b, d,
contains the six vertices b; and e.
c; d; e; f; g.
Hence, APPROX-VERTEX-COVER is a polynomial-time
2-approximation algorithm.
The traveling-salesman
problem
The traveling-salesman
problem with the
triangle inequality
• A complete undirected graph.
• Vertices lie on intersections of
integer grid lines.
• For example, f is one unit to the
right and two units up from h. The
cost function between two points
is the ordinary euclidean distance.
The traveling-salesman
problem with the
triangle inequality
• A minimum spanning tree T of the
complete graph, as computed by MST-
PRIM.
• Vertex a is the root vertex.
• Only edges in the minimum spanning
tree are shown.
• The vertices happen to be labeled in
such a way that they are added to the
main tree by MST-PRIM in alphabetical
order.
The traveling-salesman
problem with the
triangle inequality
• A walk of T , starting at vertex a.
• A preorder walk of T lists a
vertex just when it is first
encountered, as indicated by the
dot next to each vertex, yielding
the ordering a; b; c; h; d; e; f; g.
The traveling-salesman
problem with the
triangle inequality
• A tour obtained by visiting
the vertices in the order
given by the preorder walk,
which is the tour H returned
by APPROX-TSP-TOUR.
• Its total cost is
approximately 19.07.
19.0
7
14.7
Conclusion
APPROX-TSP-TOUR is a polynomial-time
2-approximation algorithm
for the traveling-salesman problem with the
triangle inequality.
The set-covering
problem
• The set-covering problem is an
optimization problem that models many
problems that require resources to be
allocated.
• Its corresponding decision problem
generalizes the NP-complete vertex-cover
problem and is therefore also NP-hard.
A greedy approximation
algorithm
Randomized
Algorithms
Randomized Algorithms
• Las Vegas
• The Las Vegas method of randomized algorithms
never gives incorrect outputs, making the time
constraint as the random variable.
• For example, Randomized Quick Sort Algorithm.
• Monte Carlo
• The Monte Carlo method of randomized
algorithms focuses on finishing the execution
within the given time constraint.
• Therefore, the running time of this method is
deterministic.
• For example, Karger’s Minimum Cut Algorithm
Kager’s Min Cut
Algorithm
• The kargers algorithm merges any two nodes in the graph into one
node which is known as a supernode.
• The edge between the two nodes is contracted and the other
edges connecting other adjacent vertices can be attached to the
supernode.
• Algorithm
• Step 1 − Choose any random edge [u, v] from the graph G to be
contracted.
• Step 2 − Merge the vertices to form a supernode and connect the edges
of the other adjacent nodes of the vertices to the supernode formed.
Remove the self nodes, if any.
• Step 3 − Repeat the process until theres only two nodes left in the
contracted graph.
• Step 4 − The edges connecting these two nodes are the minimum cut
edges.
• The algorithm does not always the give the optimal output so the
process is repeated multiple times to decrease the probability of
error.
The minimum cut of the original graph is 2 (E → D and E → F)
