| Home Page |
Author: Michael Adams
Committee
Chair: Prof. Alan Kaminsky
Reader: Prof. Stanislaw Radziszowski
Observer: Prof. Leonid Reznik
Title: A Parallel Framework for NP Combinatorial Optimization Problems
Defense Date: May 10, 2013
Abstract: NP-hard problems have no known polynomial time algorithms for finding the optimal solution. Many NP-hard problems, however, have useful similarities between them in how they are solved. This paper proposes a parallel framework developed in Java that abstracts these useful similarities for solving NP-hard problems. The framework provides a platform for solving these problems in parallel using multiple solution strategies, without the user needing to implement the strategy or the parallelism. The framework, as well as how to use it, are discussed here in detail. The development process showed that implementation time without using the framework is about twice as long as with using the framework. In addition, running the solution strategies in parallel showed a clear reduction in execution time or an increase in solution quality depending on the strategy.
Proposal: proposal.pdf
Report: report.pdf
Defense Presentation: presentation.pdf
| Home Page |