Approximation Algorithm

There are many problems in computer science, which are NP-Complete. Hence, finding an optimal solution to that problem is very hard and requires long time to execute. Thus approximation algorithms are needed to find a near-optimal solution in reasonable time. An approximation algorithm deals with these NP-complete problems. Though best solution is not guaranteed, but near-optimal solution is generated in polynomial time.

In this tutorial some problems are discussed which are generally solved by approximation algorithmic technique. Let us discuss those problems.

Subset Sum Problem

This is an optimization problem. In this problem, we wish to find a subset of {x1, x2, ... ,xn} whose sum is as large as possible but not larger than t. For example, we may have a truck that can carry no more than t pounds, and n different boxes to ship, the ith of which weighs xi pounds. We wish to fill the truck with as heavy a load as possible without exceeding the given weight limit.

Considering n number of items, we have to analyze the sums of all the possible subsets. Here, the total number of possible subsets is nC1+ nC2+nC3+...+nCn, i.e. 2n-1

Hence, the complexity of the algorithm is O(2n)

Travelling Salesman Problem

TSP is also a NP-Complete problem. Thus we need to find an approximation algorithm to get near optimal solution.

Here, we will discuss Approx-TSP using triangle inequality. To solve this, in first phase a minimum spanning tree T is determined. Then a Hamiltonian cycle is formed using pre-order traversal of the tree.

Vertex Cover Problem

A vertex cover of an graph G (V, E) is a subset of vertices V' such that for every edge e(u, v), either u ∈ V or v ∈ V or both. In this problem, the objective is to determine a vertex cover with minimum number of vertices.

The vertex cover problem is NP-complete. So, an approximation algorithm is needed to find the optimal solution. Though this algorithm does not guarantee of getting an optimal solution. But the algorithm will generate near optimal solution if reasonable time.

In this chapter, the algorithm is discussed with an example.

Happy Exploring!