A Heuristic Approach to the Consecutive Ones Submatrix Problem

Authors

Rewayda Abo-Alsabeh, Department of Mathematical Sciences, Faculty of Computer Science and Mathematics, University of Kufa, IraqFollow
Hajem Ati Daham, Department of Mathematics, College of Education for Pure Science, Al Muthanna University, IraqFollow
Abdellah Salhi, Department of Mathematical Sciences, Faculty of Science, University of Essex, UKFollow

Abstract

Given a matrix, the Consecutive Ones Submatrix (C1S) problem which aims to find the permutation of columns that maximizes the number of columns having together only one block of consecutive ones in each row is considered here. A heuristic approach will be suggested to solve the problem. Also, the Consecutive Blocks Minimization (CBM) problem which is related to the consecutive ones submatrix will be considered. The new procedure is proposed to improve the column insertion approach. Then real world and random matrices from the set covering problem will be evaluated and computational results will be highlighted.

Keywords

Consecutive Block Minimization, Consecutive Ones Property, Consecutive Ones Submatrix, Column insertion, Heuristic Approach

Article Type

Article

How to Cite this Article

Abo-Alsabeh, Rewayda; Daham, Hajem Ati; and Salhi, Abdellah (2023) "A Heuristic Approach to the Consecutive Ones Submatrix Problem," Baghdad Science Journal: Vol. 20: Iss. 1, Article 3.
DOI: https://doi.org/10.21123/bsj.2022.6373