Exploring Approximation Algorithms and Their Empirical Analysis For Selected NP-Complete Problems.

摘要

The focus of this research was on the development and testing of Approximation Algorithms for NP-Complete problems. Approximation Algorithms are algorithms that exchange accuracy for performance. They were used to approach the correct result of the NP-Complete problems within the study. NP-Complete problems are problems that currently are believed to have no feasible solution in polynomial time. The problem was to design Approximation Algorithms for each of the selected NP-Complete problems and to compare the results against an implementation of the optimal solution for restricted sized instances. The study is quantitative and involved expertise in the C++ programming language. Output from the algorithms were recorded using comma separated files and statistical tests were performed on the output for accuracy and performance. The sample size was 180 test cases wherein each test case was randomly generated input. The participants in the study are the computer algorithms to be developed and tested. The technology designed can be utilized for the development of application logic in areas such as resource management, search engines, expert systems, and computer hardware design. The findings showed that the new Approximation Algorithms were accurate within a factor of two of the optimal and that performance was significantly faster than computing the optimal. The algorithms can be used as a basis for solutions of the aforementioned business application areas or they can be used as a basis for future research.