Exploring Approximation Algorithms and Their Empirical Analysis for Selected NP-Complete Problems
Dissertation Submitted to Northcentral University Graduate Faculty of the School of Business in Partial Fulfillment of the Requirements for the Degree of
DOCTOR OF PHILOSOPHY
by Roger G. Doss
Prescott Valley, Arizona April 2011
Copyright 2011 Roger G. Doss
APPROVAL PAGE
Exploring Approximation Algorithms and Their Empirical Analysis for Selected NP-Complete Problems by
Roger G. Doss
Approved by:
_______________________________________________ ________________ Chair: Dr. James Neiman, Ph.D. Date
Member: Dr. David Bouvin, Ph.D.
Member: Dr. Steven Munkeby, D.M.
Certified by:
_______________________________________________ ________________ School Dean: A. Lee Smith, Ph.D. Date
**Abstract** 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.
**Acknowledgements** I would like to thank my committee for all the help and support that they provided me throughout this process. I would also like to thank my mother, Vicky Doss, and my fiancée, Tania Abraham, for their support and words of encouragement. I would like to dedicate this Dissertation in loving memory of my father, George Doss, who passed away in March 1998. He was the first person to call me Doctor when I was just a toddler and I have worked hard to accomplish that dream.
**Table of Contents** List of Tables ix List of Figures x Chapter 1: Introduction 1 Background 2 Problem Statement 4 Purpose 5 Theoretical Framework 7 For comparison to the optimal algorithm, each of the C++ classes designed for representing the logic of satisfiability, vertex cover, and partition, contained the logic for at least one approximation for each of the problems. The optimal algorithm shared with the approximations, the logic of streaming in and out an instance of the problem. This was designed so that each case can be recorded on disk and saved for later examination. It was also necessary to insure that the approximations were called on the same random instance as the optimal algorithm so that a comparison can be made. 18 Research Questions 18 Hypotheses 21 Nature of the Study 23 Significance of the Study 24 Definitions 24 Summary 29 Chapter 2: Literature Review 33 Algorithms 33 Complexity Theory 44 Approximation Algorithms 53 Vertex Cover 56 Partition Scheduling 66 Satisfiability 75 No Free Lunch 87 Business Applications 88 Summary 90 Chapter 3: Research Method 92 Hypotheses 95 Research Methods and Design(s) 97 Participants 100 Materials/Instruments 107 Operational Definition of Variables 124 Data Collection, Processing, and Analysis 126 Methodological Assumptions, Limitations, and Delimitations 134 Ethical Assurances 135 Summary 136 The focus of the proposed quantitative experimental study was three new approximation algorithms developed in C++. The procedure for the study was to develop approximation algorithms for three NP-Complete problems: Partition Scheduling, Vertex Cover, and 3-SAT. The approximation algorithms were compared to the optimal algorithm in terms of time and accuracy and analyzed by means of statistical tests. The measurement of time was made in terms of CPU microseconds. The measurement of correctness was made in terms of the percentage of answers that are different from the answers of the brute force algorithm. A maximum of 20 elements per instance was the input for each problem, so that brute force calculations were performed. 136 Data analysis was performed on data that is extracted from the experiment using statistical tests. The data was produced using C++ output statements that will record the running times and approximation algorithm results. These results were stored in comma separated files and later processed. The processing was done using Unix shell scripts which formatted the tables allowing for further analysis in statistical programs such as SPSS. Additionally, the shell scripts computed the aforementioned statistics regarding the accuracy of each approximation algorithm. The statistical tests performed on the formatted tables allowed for a decision to be made regarding whether or not the stated hypothesis is accepted or rejected. 136 Chapter 4: Findings 137 Results 137 H6a. The approximation algorithm for 3-SAT yielded a significantly different level of correctness compared to the optimal algorithm for 3-SAT in terms of the percentage of correct answers. 153 Evaluation of Findings 154 Summary 158 Chapter 5: Implications, Recommendations, and Conclusions 160 Implications 161 Recommendations 163 Conclusions 165 In this chapter, supporting information were presented in order for the descisions to be made to either accept or reject the hypotheses aforementioned. Based on the research findings, a conclusion was made regarding the utility of the approximation algorithms presented. The approximation algorithms performed exceptionally well, and at the same time, approached the accuracy of their respective optimal algorithms. Recommendations were made to utilize the designed framework in the development of other approximations. Additionally, the proposed approximation algorithms in this study should be used in application areas requiring solutions to the NP-Complete problems addressed. Lastly, as a future direction, an Internet Search engine can be designed utilizing the Vertex Cover approximation as a ranking methodology. 165 References 166 Appendixes 171 Appendix A: Annotated Bibliography 171 Appendix B: Optimal Algorithm 202 Appendix C: NP-Complete Problems 216 Appendix D: Data 268 |