An Efficient Technique for Optimality Measurement of Approximation Algorithms
Автор: Zahid Ullah, Muhammad Fayaz, Su-Hyeon Lee
Журнал: International Journal of Modern Education and Computer Science @ijmecs
Статья в выпуске: 11 vol.11, 2019 года.
Бесплатный доступ
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.
Graph Instances, Minimum Vertex Cover, Optimization Problem, NP-Complete Problem, Maximum Independent Set (MIS), Approximation Algorithm
Короткий адрес: https://sciup.org/15017142
IDR: 15017142 | DOI: 10.5815/ijmecs.2019.11.03
Список литературы An Efficient Technique for Optimality Measurement of Approximation Algorithms
- R. M. Karp, “Reducibility Among Combinatorial Problems”, R.E. Miller and J.W. Thatcher eds., Complexity of Computer Computations, 85-103, Plenum Press, NY, (1972).
- M. Fayaz, S. Arshad, A. S. Shah, and A.Shah, “Max Degree Around (MDA) Algorithm: A Smart and Efficient Approximate Algorithm for Vertex Cover and Independent Set Problems”, Sindh University Research Journal-SURJ (Science Series), vol. 48, no. 4D, pp. 17-26, (2016).
- X-Y. Li, Y. Wang, “Simple Approximation Algorithms and PTASs for Various Problems in Wireless Ad Hoc Networks”, Journal of Parallel and Distributed Computing, vol.66, no. 4, pp. 515-530, (2006).
- I.M. Bomze, M. Budinich, P.M. Pardalos, and M. Pelillo, "The Maximum Clique Problem," In Handbook of combinatorial optimization, Springer US, pp. 1-74, (1999).
- P. M. Pardalos, and J. Xue “The Maximum Clique Problem”, Journal of Global Optimization, vol.4, no. 3, pp.301-328, (1994).
- K. Baamann, "The Maximum Clique Problem-On Finding an Upper Bound with Application to Protein Structure Alignment", Georgia Institute of Technology, MS Thesis, (2003).
- E. Tomita, Y. Sutani, T. Higashi, and M. Wakatsuki. "A Simple and Faster Branch-and-Bound Algorithm for Finding a Maximum Clique with Computational Experiments", IEICE Transactions on Information and Systems, vol. 96-D, no. 6, pp. 1286-1298, (2013).
- S. Pollatos, "Solving the Maximum Clique Problems on a Class of Network Graphs, with Applications to Social
- Networks", Monterey, California. Naval Postgraduate School, Ph.D Thesis, (2008).
- K. L. Clarkson, "A Modification of the Greedy Algorithm for Vertex Cover", Information Processing Letters, vol. 16, pp. 23-25, (1983).
- Chvatal, V., “A Greedy Heuristic for the Set-Covering Problem”, Mathematics of Operations Research, vol.4, no.3, pp. 233-235, (1979).
- K. Imran and K. Hasham, "Modified Vertex Support Algorithm: A New Approach for Approximation of Minimum Vertex Cover", Research Journal of Computer and Information Technology Sciences, vol.1.no.6, pp. 7-11, (2013).
- Balaji, S., V. Swaminathan, and K. Kannan, “Optimization of Unweighted Minimum Vertex Cover”, World Academy of Science, International Journal of Mathematical and Computational Sciences, vol. 4, no.7, pp. 716-729, (2010).
- M. Fayaz, and S. Arshad, “Clever Steady Strategy Algorithm: A Simple and Efficient Approximation Algorithm for Minimum Vertex Cover Problem”, In Proceedings of the 2015 13th International Conference on Frontiers of Information Technology, IEEE, 14-15 December, (2015).
- I. Ahmad and M. Khan, "AVSA, Modified Vertex Support Algorithm for Approximation of MVC", International Journal of Advanced Science and Technology, vol. 67, pp. 71-78, (2014).
- Khan, I., and H. Khan, “Degree Contribution Algorithm for Approximation of MVC”, International Journal of Hybrid Information Technology, vol. 7, no. 5, pp. 183-190, (2014).
- M. Fayaz, S. Arshad, A.S. Shah, and A. Shah, “An Optimal Approximation Algorithm for Optimization of Un-Weighted Minimum Vertex Cover Problem”, Sindh University Research Journal-SURJ (Science Series), vol. 48, no. (4D), pp. 175-182, (2016).
- M. Fayaz, S. Arshad, U. Zaman, and A. Ahmad. "A Simple, Fast and Near Optimal Approximation Algorithm for Optimization of Un-weighted Minimum Vertex Cover", In Frontiers of Information Technology (FIT), 2016 International Conference on, IEEE, pp. 176-180, (2016).
- https://turing.cs.hbg.psu.edu/txn131/vertex_cover.html (accessed 15 March 2019)
- http://sites.nlsde.buaa.edu.cn/~kexu/benchmarks/graph-benchmarks.htm (accessed 15 March 2019).
