Approximation Algorithms (Introduction)

In this article we will be exploring an interesting as well as deep overview of Approximation Algorithms, but before that we will be discussing some important terms.

Optimization Problems

In computer science many a times we come across optimization problems, where we have to optimize a certain variable in accordance to some other variables. Optimization means finding maximum or minimum.
For example,

1. Finding the shortest path between two vertices in a graph.
2. Finding the minimum number of colors needed to color a graph, etc.

Decision Problems

These are a little bit different than the Optimization poblems. In these type of problems the main target is to find weather a solution exists or not, just like a typical yes or no question.
For example,

1. Checking if a graph is Hamiltonian
2. Checking weather a cycle exists in a Linked List, etc.

Programming and mathematical problems that we have observed in daily life can be categorize into two classes of problems,

• P class
• NP class

P class

The class P consists of those problems that are solvable in polynomial time by the turing machine, i.e. these problems can be solved in time O(n^k) in worst-case, where k is constant.These problems are also known as tractable.

An algorithm A is a polynomial time algorithm, if there exists a polynomial p(n) such that the algorithm can solve any instance of size n in a time O(p(n)).
Algorithms such as Matrix Chain Multiplication, Single Source Shortest Path, All Pair Shortest Path, Minimum Spanning Tree, etc. run in polynomial time.

NP class

NP is the class of decision problems for which it is easy to check the correctness of a claimed answer, with the aid of a little extra information. NP consists of those problems that are verifiable in polynomial time. Hence, we aren’t asking for a way to find a solution, but only to verify that an alleged solution really is correct.

Every problem in this class can be solved in exponential time using exhaustive search.
Problems such as traveling salesperson, optimal graph coloring,Hamiltonian cycles etc for which no polynomial time algorithms is known, are classified as NP complete problems.

Approximation Algorithms

Formal definitation says,

Given an optimization problem P, an algorithm A is said to be an approximate algorithm for P, if for any given instance I, it returns an approximate solution i.e. a feasible solution.

An Approximation Algorithm is a way of approach NP-completeness for any optimization problem. This does not guarantee the best solution. The main purpose of an approximation algorithm is to come as close as possible to the optimum value in at the most polynomial time. Such algorithms are called approximation algorithms.

For example -For the traveling salesperson problem, the optimization problem is to find the shortest cycle, and the approximation problem is to find a short cycle.

Some famous problems of Approximation Algorithms

1. The Vertex Cover Problem

Problem Statement
Given an undirected graph, the vertex cover problem is to find minimum size vertex cover.
As the name suggests, A vertex cover of an undirected graph is a subset of its vertices such that for every edge (x, y) of the graph, either x or y is in vertex cover.
This problem is a NP-complete problem and can be solved approximately i.e. no polynomial time solution(unless P = NP).

1) Initialize the result as an empty list {}
2) Consider a set of all edges in given graph.  Let the set be E.
3) while E is not empty
    a) Pick an arbitrary edge (x, y) from set E and add x and y to result
    b) Remove all edges from E which are either incident on x or y.
4) Return result 

The time complexity of the above algorithm is O(V+E) where V is the number of vertices in the graph and E is the number of edges.

2. The Travelling Salesman Problem

Problem Statement
Given a set of cities and distance between every pair of cities, the problem is to find the shortest possible route that visits every city exactly once and returns to the starting point.

This problem can be converted into a graph problem, which has V nodes(i.e. number of cities) and the cost matrix will hold the edge weights(i.e. the distance between any two cities).
The problem is a famous NP hard problem. There is no polynomial time know solution for this problem.

A naive approach to solve the problem can be,

1) Consider city 1 as the starting and ending point.
2) Generate all (V-1)! Permutations of cities.
3) Calculate cost of every permutation and keep track of minimum cost permutation.
4) Return the permutation with minimum cost.

The above algorithm works in O(V!) time complexity, where V is the number of vertices in the graph.

There are other approaches using Bitmasking and Dynamic Programming to solve in O(V^2 * 2^V) time complexity.
Branch and Bound can be one approach in finding a solution for this NP Hard problem.

This problem can be easier to approximate if the edge weights of the graph follow a traingle inequality, which means w(u,v) <= w(u,x) + w(x,v), i.e. distance of city u to city v is less than the sum of distance of city u to city x and city x to city v. This problem is also known as Metric TSP, which is an approximate version of the problem. This is still NP Hard, but we can approximate the solution.

3. The Bin Packing Problem

Problem Statement
Given n items of different weights and bins each of capacity c, assign each item to a bin such that number of total used bins is minimized. It may be assumed that all items have weights smaller than bin capacity.
In computational mathematics, this problem is a NP Hard problem and the decision problem version of the same is NP Complete.

This problem has been studied widely and can be solved in many approximation techniques like - Next-Fit (NF), Next-k-Fit (NkF), First-Fit (FF), Best-Fit (BF), Worst-Fit (WF), First Fit Decreasing (FFD) etc.

The best time complexity can be O(NlogN) for this.

Examples of Approximation Algorithms

The approximation algorithms return us a legal solution that may not be optimized, let's have a look at the below examples,

1 - The vertex cover problem -
Given an undirected graph, the vertex cover problem is to find minimum size vertex cover, this is an optimized return type, i.e. we need to minimize the size of the vertex cover.
But the approximation version can be compiled as,Given an undirected graph, the vertex cover problem is to find the vertex cover, you may notice that there is no optimization(min/max requirement).

Similarly,
2 - The Travelling Salesman Problem
Given a set of cities and distance between every pair of cities, the problem is to find the possible route that visits every city exactly once and returns to the starting point.
Notice that we don't need to find the shortest(i.e. minimum) possible root, instead we just need to find a legal route for our salesman.

Conclusion

The above problems are some of the examples to deliver the idea of what an Approximation Problem looks like. There are several other problems as well which are NP hard and NP complete.
The best thing about approximation algorithms is that, you can cross proof your approach in order to know if that's a feassible one.
And the probable worst thing is, these are approximations not exact.
Algorithms rule the world even if that is approximate or exact. Hence let's utilize these rules to build a better world for everyone.