NP-Hard problems using Map-Reduce
Department of Computer Science
B. Thomas Golisano College of Computing and Information
Sciences Rochester Institute of Technology
This project focuses on three NP-hard problems, Max-K Cover problem, Maximum Clique problem and Subset Sum problem. The Max-K Cover problem is to select K sets from a collection of sets in order to maximize the size of the union. Currently, a favorite approach to solve Max-K Cover problem is a greedy algorithm, which selects the largest set and removes its elements from the other sets.