Posts

Showing posts from 2014

Lecture on Recommender Systems

Great lecture on Recommender Systems by   Xavier Amatriain,  Researcher on Netflix.  https://www.youtube.com/watch?v=bLhq63ygoU8 https://www.youtube.com/watch?v=mRToFXlNBpQ

Genetic Algorithm for Knapsack using Hadoop

Image
Development of Genetic Algorithm using Apache Hadoop framework to solve optimization problems Introduction This project I developed during a course on my Master intends to construct a Genetic algorithm to solve optimization problems, focusing on the Knapsack Problem. It uses as base the distributed framework Apache Hadoop. The idea is to show that the MapReduce paradigm implemented by Hadoop is a good fit for several NP-Complete optimization problems. As knapsack, many problems present a simple structure and converge to optimal solutions given a proper amount of computation. Genetic Algorithm The algorithm was developed based on a Genetic paradigm. It starts with a initial random population (random instances to the problem). Then, the best individuals are selected among the population (instances that generate the best profits for the knapsack). A phase of crossover was then implemented to generate new instances as combination of the selected indi

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