Abstract
ThefocusofthisresearchwasonthedevelopmentandtestingofApproximation
AlgorithmsforNP-Completeproblems.ApproximationAlgorithmsarealgorithmsthat
exchangeaccuracyforperformance.TheywereusedtoapproachthecorrectresultoftheNP-
Completeproblemswithinthestudy.NP-Completeproblemsareproblemsthatcurrentlyare
believedtohavenofeasiblesolutioninpolynomialtime.Theproblemwastodesign
ApproximationAlgorithmsforeachoftheselectedNP-Completeproblemsandtocompare
theresultsagainstanimplementationoftheoptimalsolutionforrestrictedsizedinstances.
ThestudyisquantitativeandinvolvedexpertiseintheC++programminglanguage.Output
fromthealgorithmswererecordedusingcommaseparatedfilesandstatisticaltestswere
performedontheoutputforaccuracyandperformance.Thesamplesizewas180testcases
whereineachtestcasewasrandomlygeneratedinput.Theparticipantsinthestudyarethe
computeralgorithmstobedevelopedandtested.Thetechnologydesignedcanbeutilizedfor
thedevelopmentofapplicationlogicinareassuchasresourcemanagement,searchengines,
expertsystems,andcomputerhardwaredesign.Thefindingsshowedthatthenew
ApproximationAlgorithmswereaccuratewithinafactoroftwooftheoptimalandthat
performancewassignificantlyfasterthancomputingtheoptimal.Thealgorithmscanbeused
asabasisforsolutionsoftheaforementionedbusinessapplicationareasortheycanbeused
asabasisforfutureresearch.
