# Approximation Algorithms

**Overview :**

An approximation algorithm is a way of dealing with NP-completeness for an optimization problem. The goal of the approximation algorithm is to come close as much as possible to the optimal solution in polynomial time.

**Features of**** Approximation Algorithm**** : **

Here, we will discuss the features of the Approximation Algorithm as follows.

Attention reader! Don’t stop learning now. Practice GATE exam well before the actual exam with the subject-wise and overall quizzes available in **GATE Test Series Course**.

Learn all **GATE CS concepts with Free Live Classes** on our youtube channel.

- An approximation algorithm guarantees to run in polynomial time though it does not guarantee the most effective solution.
- An approximation algorithm guarantees to seek out high accuracy and top quality solution(say within 1% of optimum)
- Approximation algorithms are used to get an answer near the (optimal) solution of an optimization problem in polynomial time

**Performance Ratios for approximation algorithms :**

Here, we will discuss the performance ratios of the Approximation Algorithm as follows.

**Scenario-1 :**

- Suppose that we are working on an optimization problem in which each potential solution has a cost, ad we wish to find a near-optimal solution. Depending on the problem, we may define an optimal solution as one with maximum possible cost or one with minimum possible cost,i.e, the problem can either be a maximization or minimization problem.
- We say that an algorithm for a problem has an appropriate ratio of P(n) if, for any input size n, the cost C of the solution produced by the algorithm is within a factor of P(n) of the cost C* of an optimal solution as follows.

max(C/C*,C*/C)<=P(n)

**Scenario-2 :**

If an algorithm reaches an approximation ratio of P(n), then we call it a P(n)-approximation algorithm.

- For a maximization problem, 0< C < C×, and the ratio of C/C* gives the factor by which the cost of an optimal solution is larger than the cost of the approximate algorithm.
- For a minimization problem, 0< C* < C, and the ratio of C/C* gives the factor by which the cost of an approximate solution is larger than the cost of an optimal solution.

**Some examples of Approximation algorithm :**

Here, we will discuss some examples of the Approximation Algorithm as follows.

**The Vertex Cover Problem****–**

In the vertex cover problem, the optimization problem is to select a minimum number of vertices that should cover all the edges in a graph.

**Travelling Salesman Problem****–**

In the Travelling Salesman Problem, the optimization problem is that the salesman has to take a route that has a minimum cost.

**The Set Covering Problem****–**

This is an optimization problem that models many problems that require resources to be allocated. Here, a logarithmic approximation ratio is used.

**The Subset Sum Problem****–**

In the Subset sum problem, the optimization problem is to find a subset of {x1,×2,×3…xn} whose sum is as large as possible but not larger than target value t.