Exploring Approximation Algorithms and Their Empirical Analysis for Selected np-complete Problems




НазваниеExploring Approximation Algorithms and Their Empirical Analysis for Selected np-complete Problems
страница1/35
Дата27.11.2012
Размер1.16 Mb.
ТипДокументы
  1   2   3   4   5   6   7   8   9   ...   35


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
  1   2   3   4   5   6   7   8   9   ...   35

Похожие:

Exploring Approximation Algorithms and Their Empirical Analysis for Selected np-complete Problems iconOn np-complete Problems and Approximation Algorithms

Exploring Approximation Algorithms and Their Empirical Analysis for Selected np-complete Problems iconSimulation and Analysis of Adaptive Beamforming Algorithms for Phased Array Antennas

Exploring Approximation Algorithms and Their Empirical Analysis for Selected np-complete Problems iconDesign Methods and Analysis of Algorithms 4 csm102 Object Oriented Programming through java

Exploring Approximation Algorithms and Their Empirical Analysis for Selected np-complete Problems iconA comparative analysis of the science and innovation profiles of oecd and selected countries

Exploring Approximation Algorithms and Their Empirical Analysis for Selected np-complete Problems iconThe analysis of the splitting error for advection-reaction problems in air pollution models

Exploring Approximation Algorithms and Their Empirical Analysis for Selected np-complete Problems iconTrainees’ Marketability Of Selected Youth Pre-Employment Training Program: a multinomial Logistic Regression Analysis

Exploring Approximation Algorithms and Their Empirical Analysis for Selected np-complete Problems iconLinear programming approach to nonlinear deterministic and stochastic control problems: perturbations methods and numerical analysis

Exploring Approximation Algorithms and Their Empirical Analysis for Selected np-complete Problems iconGorbachenko V. I., Artyuhina E. V. Meshless neural network algorithm solving boundary value problems, based on the approximation of the nonlinear dependence
Горбаченко В. И., Артюхина Е. В. Бессеточные нейросетевые алгоритмы решения краевых задач, основанные на аппроксимации нелинейных...
Exploring Approximation Algorithms and Their Empirical Analysis for Selected np-complete Problems icon1. Shiwei Yu,Yi-Ming Wei, Jingli Fan, et al. Exploring the regional characteristics of inter -provincial co2 emissions in China: An improved fuzzy clustering analysis based on particle swarm optimization j applied Energy, 2012,42(3): 521-529. ( 国际期刊 sci &EI, if: 915)

Exploring Approximation Algorithms and Their Empirical Analysis for Selected np-complete Problems iconЗадачам по физике. The present article considers application of morphological analysis and elements of triz to physics contests problems
Ключевые слова: олимпиадные задачи по физике, приёмы составления задач, приёмы решения задач
Разместите кнопку на своём сайте:
Библиотека


База данных защищена авторским правом ©lib.znate.ru 2014
обратиться к администрации
Библиотека
Главная страница