A Metaheuristic Approach to the C1S Problem

  • Rewayda Abo-Alsabeh Department of Mathematical Sciences, University of Kufa, Alnajif, Iraq
  • Abdellah Salhi Department of Mathematical Sciences, University of Essex, UK
Keywords: Approximation algorithm,, Genetic algorithm,, Consecutive Ones Property,, Consecutive Block Minimization.

Abstract

Given a binary matrix, finding the maximum set of columns such that the resulting submatrix has the Consecutive Ones Property (C1P) is called the Consecutive Ones Submatrix (C1S) problem. There are solution approaches for it, but there is also a room for improvement. Moreover, most of the studies of the problem use exact solution methods. We propose an evolutionary approach to solve the problem. We also suggest a related problem to C1S, which is the Consecutive Blocks Minimization (CBM). The algorithm is then performed on real-world and randomly generated matrices of the set covering type.  

Published
2021-01-30
How to Cite
Abo-AlsabehR., & SalhiA. (2021). A Metaheuristic Approach to the C1S Problem. Iraqi Journal of Science, 62(1), 218-227. https://doi.org/10.24996/ijs.2021.62.1.20
Section
Mathematics