Most Valuable Player Algorithm for Solving Minimum Vertex Cover Problem

Minimum Vertex Cover Problem (MVCP) is a combinatorial optimization problem that is utilized to formulate multiple real-life applications. Owing to this fact, abundant research has been undertaken to discover valuable MVCP solutions. Most Valuable Player Algorithm (MVPA) is a recently developed metaheuristic algorithm that inspires its idea from team-based sports. In this paper, the MVPA_MVCP algorithm is introduced as an adaptation of the MVPA for the MVCP. The MVPA_MVCP algorithm is implemented using Java programming language and tested on a Microsoft Azure virtual machine. The performance of the MVPA_MVCP algorithm is evaluated analytically in terms of run time complexity. Its average-case run time complexity is ceased to Θ(I(|V|+|E|)), where I is the size of the initial population, |V| is the number of vertices and |E| is the number of edges of the tested graph. The MVPA_MVCP algorithm is evaluated experimentally in terms of the quality of gained solutions and the run time. The experimental results over 15 instances of DIMACS benchmark revealed that the MVPA_MVCP algorithm could, in the best case, get the best known optimal solution for seven data instances. Also, the experimental findings exposed that there is a direct relation between the number of edges of the graph under test and the run time.

@article{Khattab2019,
  title     = {Most Valuable Player Algorithm for Solving Minimum Vertex Cover Problem},
  journal   = {International Journal of Advanced Computer Science and Applications},
  volume    = {10},
  number    = {8},
  year      = {2019},
  publisher = {The Science and Information Organization},
  author    = {Hebatullah Khattab and Ahmad Sharieh and Basel A. Mahafzah},
  doi       = {10.14569/IJACSA.2019.0100821},
  url       = {https://doi.org/10.14569/IJACSA.2019.0100821}
}