Minimising the number of gap-zeros in binary matrices

Article English OPEN
Glass, CA ; Shakhlevich, NV (2013)
  • Publisher: Elsevier

We study a problem of minimising the total number of zeros in the gaps between blocks of consecutive ones in the columns of a binary matrix by permuting its rows. The problem is referred to as the Consecutive Ones Matrix Augmentation Problem, and is known to be NP-hard. An analysis of the structure of an optimal solution allows us to focus on a restricted solution space, and to use an implicit representation for searching the space. We develop an exact solution algorithm, which is linear-time in the number of rows if the number of columns is constant, and two constructive heuristics to tackle instances with an arbitrary number of columns. The heuristics use a novel solution representation based upon row sequencing. In our computational study, all heuristic solutions are either optimal or close to an optimum. One of the heuristics is particularly effective, especially for problems with a large number of rows.
  • References (22)
    22 references, page 1 of 3

    [1] F. Alizadeh, R. M. Karp, L. A. Newberg, and D. K. Weisser, Physical mapping of chromosomes: a combinatorial problem in molecular biology, Algorithmica 13 (1995), 52-76.

    [2] F. Alizadeh, R. M. Karp, D. K. Weisser, and G. Zweig, Physical mapping of chromosomes using unique probes, Journal of Computational Biology 2 (1995), 159-184.

    [3] J. E. Atkins, E. G. Boman, and B. Hendrickson, A spectral algorithm for seriation and the consecutive ones problem, SIAM Journal on Computing 28 (1998), 297-310.

    [4] J. E. Atkins and M. Middendorf, On physical mapping and the consecutive ones property for sparse matrices, Discrete Applied Mathematics 71 (1996), 23-40.

    [5] K. S. Booth, PQ-tree algorithms, Ph.D. thesis, University of California, Berkeley, US, 1975.

    [6] K. S. Booth and G. S. Lueker, Test for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms, Journal of Computer and System Sciences 13 (1976), 335-379.

    [7] K. Chakhlevitch, C. A. Glass, and H. Kellerer, Batch machine production with perishability time windows and limited batch size, European Journal of Operational Research 210 (2011), 39-47.

    [8] K. Chakhlevitch, C. A. Glass, and P. A. Sadd, Applying efficient logistics in a microbiology laboratory, Journal of Food Engineering 103 (2011), 377-387.

    [9] M. Dom, Algorithmic aspects of the Consecutive-Ones Property, EATCS Bulletin 98 (2008), 27-59.

    [10] M. Dom, J. Guo, and R. Niedermeier, Approximation and fixed-parameter algorithms for consecutive ones submatrix problems, Journal of Computer and System Sciences 76 (2010), 204-221.

  • Metrics
    views in OpenAIRE
    views in local repository
    downloads in local repository

    The information is available from the following content providers:

    From Number Of Views Number Of Downloads
    White Rose Research Online - IRUS-UK 0 56
Share - Bookmark