An Efficient Technique for Optimality Measurement of Approximation Algorithms

Zahid Ullah, Muhammad Fayaz, Su Hyeon Lee

Research output: Contribution to journalArticlepeer-review

3 Scopus citations

Abstract

Many algorithms have been proposed for the solution of the minimum vertex cover (MVC) problem, but the researchers are unable to find the optimality of an approximation algorithm. In this paper, we have proposed a method to evaluate that either the result returned by an approximation algorithm for the minimum vertex cover problem is optimal or not. The proposed method is tested on three algorithms, i.e., maximum degree greedy (MDG) algorithm, modified vertex support algorithm (MVSA) and clever steady strategy algorithm (CSSA). The proposed method provides an opportunity to test the optimality of an approximation algorithm for MVC problem with low computation complexity. The proposed method has performed well during experimentation, and its results brighten the path of successful implementation of the method for the evaluation of approximation algorithms for the minimum vertex cover (MVC) problem. The testing of the proposed method was carried out on small graph instances. The proposed method has resolved the problem to test the optimality of the approximation algorithm for the minimum vertex cover problem. This technique has digitized the process of finding out the accuracy of the optimal solution returned by approximation algorithms for MVC.

Original languageEnglish
Pages (from-to)13-21
Number of pages9
JournalInternational Journal of Modern Education and Computer Science
Volume11
Issue number11
DOIs
StatePublished - Nov 2019

Keywords

  • Approximation Algorithm
  • Graph Instances
  • Maximum Independent Set (MIS)
  • Minimum Vertex Cover
  • NP-Complete Problem
  • Optimization Problem

Fingerprint

Dive into the research topics of 'An Efficient Technique for Optimality Measurement of Approximation Algorithms'. Together they form a unique fingerprint.

Cite this