A Heuristic Approach to the Consecutive Ones Submatrix Problem
DOI:
https://doi.org/10.21123/bsj.2022.6373Keywords:
Consecutive Block Minimization, Consecutive Ones Property, Consecutive Ones Submatrix, Column insertion, Heuristic ApproachAbstract
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.
Received 26/5/2021
Accepted 3/4/2022
Published Online First 20/7/2022
References
Fulkerson D, Gross O. Incidence matrices and interval graphs. Pac J Math. 1965; 15(3): 835-855.
Haddadi S, Chenche S, Cheraitia M, Guessoum F. Polynomial time local-improvement algorithm for consecutive block minimization. Inf Process Lett. 2015; 115(6): 612-617.
Tan J, Zhang L. The consecutive ones submatrix problem for sparse matrices. Algorithmica. 2007; 48(3): 287-299.
Dom M, Guo J, Niedermeier R. Approximation and fixed-parameter algorithms for consecutive ones submatrix problems. J Comput Syst Sci. 2010; 76(3): 204-221.
Tucker A A structure theorem for the consecutive 1's property. J Comb Theory Ser B. 1972; 12(2): 153-162.
Safe MD. Circularly compatible ones, d-circularity, and proper circular-arc bigraphs. arXiv preprint arXiv. 1906.00321. 2019.
Pardal N. Structural characterization of some problems on circle and interval graphs. arXiv preprint arXiv. 2006.00099, 2020.
Safe MD. Characterization and linear-time detection of minimal obstructions to concave-round graphs and the circular-ones property. J Graph Theory. 2020; 93(2): 268-298.
Pardal N, Durán GA, Grippo LN, Safe MD, On nested and 2-nested graphs: two subclasses of graphs between threshold and split graphs. arXiv preprint arXiv. 1906.11970, 2019.
Cao Y, Grippo LN, Safe MD. Forbidden induced subgraphs of normal helly circular-arc graphs: Characterization and detection. Discret Appl Math. 2017;216:67-83.
De Luca F, Hossain MI, Kobourov S, Lubiw A, Mondal D. Recognition and drawing of stick graphs. Theor Comput Sci. 2019; 796:22-33.
Meidanis J, Porto O, Telles GP. On the consecutive ones property. Discrete Appl Math. 1998; 88(1): 325-354.
Booth KS, Lueker GS. Testing for the consecutive ones property, interval graphs, and gr aph planarity using PQ-tree algorithms. J Comput Syst Sci. 1976; 13(3): 335-379.
Hajiaghayi MT, Ganjali Y. A note on the consecutive ones submatrix problem. Inf Process Lett. 2002; 83(3): 163-166.
Haddadi S. Benders decomposition for set covering problems. J Comb Optim. 2017; 33(1): 60-80.
Soares LC, Reinsma JA, Nascimento LH, Carvalho MA. Heuristic methods to consecutive block minimization. Comput Oper Res. 2020; 120: 104948.
Abo-Alsabeh R, Salhi A. A Metaheuristic approach to the C1S problem. Iraqi J Sci. 2021; 62 (1): 218-227.
Subashini R, Rani MR, Jagalmohanan M.Simultaneous consecutive ones submatrix and editing problems: Classical complexity and fixed-parameter tractable results. Theor Comput Sci. 2020; 812: 13-38.
Kendall D. Incidence matrices, interval graphs and seriation in archaeology. Pac J Math. 1969; 28(3): 565-570.
Abduljabbar IA, Abdullah SM. An Evolutionary Algorithm for Solving Academic Courses Timetable Scheduling Problem. Baghdad Sci J. 2022; 19(2): 0399-0399.
Iqbal Z, Ilyas R, Chan HY, Ahmed N. Effective Solution of University Course Timetabling using Particle Swarm Optimizer based Hyper Heuristic approach. Baghdad Sci J. 2021; 18(4): 1465-1465.
Ruf N, Scho ̈bel AA. Set covering with almost consecutive ones property. Discrete Optim. 2004; 1(2): 215-228.
Downloads
Published
Issue
Section
License
Copyright (c) 2022 Baghdad Science Journal
This work is licensed under a Creative Commons Attribution 4.0 International License.
How to Cite
