APPROXIMATION ALGORITHMS

 INTRODUCTION

An Approximate Algorithm is a way of approach NP-COMPLETENESS for the 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 the most polynomial time. Such algorithms are called approximation algorithm or heuristic algorithm.

1.For the travelling salesperson problem, the optimization problem is to find the shortest cycle, and the approximation problem is to find a short cycle.

2.For the vertex cover problem, the optimization problem is to find the vertex cover with fewest vertices, and the approximation problem is to find the vertex cover with few vertices.

FEATURES OF APPROXIMATION ALGORITHM

1.An approximation algorithm guarantees to run in polynomial time though it does not guarantee the most effective solution.

2.An approximation algorithm guarantees to seek out high accuracy and top quality solution.

3.Approximation algorithms are used to get an answer near the (optimal) solution of an optimization problem in polynomial time.

PERFORMANCE RATIOS FOR APPROXIMATION ALGORITHM 

Suppose we work on an optimization problem where every solution carries a cost. An Approximate Algorithm returns a legal solution, but the cost of that legal solution may not be optimal.

      For Example, suppose we are considering for a minimum size vertex-cover (VC). An approximate algorithm returns a VC for us, but the size (cost) may not be minimized.

      Another Example is we are considering for a maximum size Independent set (IS). An approximate Algorithm returns an IS for us, but the size (cost) may not be maximum. Let C be the cost of the solution returned by an approximate algorithm, and C* is the cost of the optimal solution.

    We say the approximate algorithm has an approximate ratio P (n) for an input size n, where

Intuitively, the approximation ratio measures how bad the approximate solution is distinguished with the optimal solution. A large (small) approximation ratio measures the solution is much worse than (more or less the same as) an optimal solution.

EXAMPLES OF APPROXIMATION ALGORITHM

1.VERTEX COVER PROBLEM

A vertex cover of an undirected graph is a subset of its vertices such that for every edge (u, v) of the graph, either ‘u’ or ‘v’ is in the vertex cover. Although the name is Vertex Cover, the set covers all edges of the given graph. Given an undirected graph, the vertex cover problem is to find minimum size vertex cover.

Approximate Algorithm for Vertex Cover

A simple approximate algorithm for the vertex cover problem is :

· Initialize the vertex cover set as empty.

· Let the set of all edges in the graph be called E.

· While E is not empty:

o Pick a random edge from the set E, add its constituent nodes, u and v into the vertex cover set.

o For all the edges, which have either u or v as their part, remove them from the set E.

· Return the final obtained vertex cover set, after the set E is empty.

It can be proven that the above algorithm will always find a vertex cover that is never greater than twice the size of the optimal vertex cover for the given graph.

2.TRAVELLING SALESMAN PROBLEM

In the travelling salesman Problem, a salesman must visits n cities. We can say that salesman wishes to make a tour or Hamiltonian cycle, visiting each city exactly once and finishing at the city he starts from. There is a non-negative cost c (i, j) to travel from the city i to city j. The goal is to find a tour of minimum cost. We assume that every two cities are connected. Such problems are called Travelling-salesman problem (TSP).

We can model the cities as a complete graph of n vertices, where each vertex represents a city.

 It can be shown that TSP is NPC.

 If we assume the cost function c satisfies the triangle inequality, then we can use the following approximate algorithm.

TRIANGLE INEQUALITY

Let u, v, w be any three vertices, we have

One important observation to develop an approximate solution is if we remove an edge from H*, the tour becomes a spanning tree.

Approx-TSP (G= (V, E))    

  1. Compute a MST T of G; 

  2. Select any vertex r is the root of the tree; 

  3. Let L be the list of vertices visited in a preorder tree walk of T; 

  4. Return the Hamiltonian cycle H that visits the vertices in the order L;  

Intuitively, Approx-TSP first makes a full walk of MST T, which visits each edge exactly two times. To create a Hamiltonian cycle from the full walk, it bypasses some vertices (which corresponds to making a shortcut)

CONCLUSION

Many interesting problems involve shifting through a large amount of the data to make an informed decision Most of the problem of interest That is real world problem are discrete optimization problem which are np hard this means that the number of operations required to find an optimal solution grows exponentially with the problem size typically exponential growth rates involves doubling the number of operations for each additional element added to the set.

Unless it turns out np hard we will not be able to find the optimal solution for all members of a particular problem class  in polynomial time in other words we must give up on one of the following requirements always find optimal solution in polynomial time for any problem instance.