Posts

Showing posts from January, 2014

Dealing with NP-Hard Problems: An Introduction to Approximation Algorithms

Image
This is just a quick overview on approximation algorithms. It is a broad topic to discuss. For more info rmation go to References. The famous NP-Complete class is known for its possible intractability. NP means non deterministic polynomial and for a problem to be NP-Complete it has to be   NP  (verified in polynomial time) and   NP-Hard (as hard as any other problem in the NP class). Among the several important problems that are NP-Complete or NP-Hard (on its optimization form) we can name the Knapsack, the Travel Salesmen, and the Set Cover problem. Even though no efficient optimal solution might exist for NP-Complete problems we still need to address this issue due to the amount of practical problems existent in the NP-Complete class. Considering that even for medium volumes of data exponential brute-force is impractical, the option is abdicating the optimum solution as minimum as possible and pursuing an efficient algorithm.   Approximation algorithms are a way