Approximation Algorithm Explained

Here we are going to learn about the very famous algorithm that gives near possible solution when there is no efficient solution to a given problem. As I mentioned above this technique can be applied when we don’t need the exact solution to a problem, but a solution that is near to the solution.This is called Approximation algorithm.

This technique doesn’t promise the exact the solution, but they assure the approximate to final solution. And it will lead you to the mental shortcuts that helps to make a decision towards the exact solution.

If you have a basic knowledge of these technical terms like Basic data structures, Basic Sorting algorithm and Graphs Terms and representations, then you are good to go ahead with reading this article.

Happy Reading! and any suggestions are welcome.

Background –

Polynomial is expression contains Constants, Variables and exponents where the arithmetic operations like addition, subtraction and multiplication is allowed but not division. This is basically used to measure the complexity approximation. Polynomial time algorithm is better than their exponential.

The debate is P=NP or P≠NP , so many works to prove each is true!! But we can’t stop in the dilemma and there are so many real world problems which belongs to this categories. If a problem is NP-complete, we are doubtful to find a polynomial time algorithm for solving it exactly, but this does not infer that all hope is lost.
There are two methods to getting around NP-completeness.
First, if the actual inputs are small, an algorithm with exponential running time may be perfectly satisfactory.
Second, it may still be possible to find near-optimal solutions in polynomial time, so we need to come with alternative to the deterministic algorithm such one algorithm is Approximation algorithm.

Goal of Approximation algorithm is to find an algorithm so that the approximation factor is small as possible so that we are as much as possible close to the exact solution ensuring the polynomial time. And it is best that the approximation algorithm complexity can be calculated using input size and approximation factor.

Below are the 2 examples,

1. For the Vertex Cover problem -

a. Smallest vertex which covers the graph is called Vertex Cover and Finding the smallest vertex covered is NP hard problem

b. The approximation problem is to discovery a Vertex cover with few vertices.

2. For Traveling salesman Problem (TSP) –

a. Problem is to find the shortest Cycle

b. Approximation problem is to find the short Cycle.

Input — A Complete Graph G with n vertices -G(V,E), w as weight of edge value

Output — Cycle V1, V2…Vn, V1 where each edge visited only once

Goal — to find the minimum weight of the cycle covering all the edges.

Weight = w(V1,V2)+w(V2,V3)+….+W(Vm-1,Vm)+(Vm,V1)

The approximation algorithm we find here should be more than the minimum weigh of the Traveling Salesman problem

Below is the approximation solution for TSP

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

{

Compute a MST T of G;

Select any vertex r is the root of the tree;

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

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

}

Approximation Algorithm Techniques, which intern are a individual topics can be studied further

1. Greedy Algorithm

2. Primal Dual Algorithm

3. Linear Programming and Rounding

4. Integer Programming

Thanks for Reading , Please clap so this article will be appeared in others search.