×

Minimising the number of gap-zeros in binary matrices. (English) Zbl 1317.90252

Summary: 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.

MSC:

90C27 Combinatorial optimization
90B35 Deterministic scheduling theory in operations research
90C59 Approximation methods and heuristics in mathematical programming
90C09 Boolean programming
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Alizadeh, F.; Karp, R. M.; Newberg, L. A.; Weisser, D. K., Physical mapping of chromosomes: a combinatorial problem in molecular biology, Algorithmica, 13, 52-76 (1995) · Zbl 0831.92012
[2] Alizadeh, F.; Karp, R. M.; Weisser, D. K.; Zweig, G., Physical mapping of chromosomes using unique probes, Journal of Computational Biology, 2, 159-184 (1995) · Zbl 0870.92005
[3] Atkins, J. E.; Boman, E. G.; Hendrickson, B., A spectral algorithm for seriation and the consecutive ones problem, SIAM Journal on Computing, 28, 297-310 (1998) · Zbl 0930.05064
[4] Atkins, J. E.; Middendorf, M., On physical mapping and the consecutive ones property for sparse matrices, Discrete Applied Mathematics, 71, 23-40 (1996) · Zbl 0876.92011
[6] Booth, K. S.; Lueker, G. S., Test for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms, Journal of Computer and System Sciences, 13, 335-379 (1976) · Zbl 0367.68034
[7] Chakhlevitch, K.; Glass, C. A.; Kellerer, H., Batch machine production with perishability time windows and limited batch size, European Journal of Operational Research, 210, 39-47 (2011) · Zbl 1207.90053
[8] Chakhlevitch, K.; Glass, C. A.; Sadd, P. A., Applying efficient logistics in a microbiology laboratory, Journal of Food Engineering, 103, 377-387 (2011)
[9] Dom, M., Algorithmic aspects of the consecutive-ones property, EATCS Bulletin, 98, 27-59 (2008) · Zbl 1179.05071
[10] Dom, M.; Guo, J.; Niedermeier, R., Approximation and fixed-parameter algorithms for consecutive ones submatrix problems, Journal of Computer and System Sciences, 76, 204-221 (2010) · Zbl 1201.68153
[11] Fulkerson, D. R.; Gross, O. A., Incidence matrices and interval graphs, Pacific Journal of Mathematics, 15, 835-855 (1965) · Zbl 0132.21001
[12] Garey, M. R.; Johnson, D. S., Computers and Intractability: A Guide to the Theory of NP-Completeness (1979), W.H. Freeman: W.H. Freeman San Francisco · Zbl 0411.68039
[13] Ghosh, S. P., File organization: the consecutive retrieval property, Communications of ACM, 15, 802-808 (1972) · Zbl 0246.68004
[14] Greenberg, D. S.; Istrail, S., Physical mapping by STS hybridization: algorithmic strategies and the challenge of software evaluation, Journal of Computational Biology, 2, 219-273 (1995)
[15] Habib, M. T.; McConnell, R.; Paul, C.; Viennot, L., Lex-BFS and partition refinement, with applications to the transitive orientation, interval graph recognition and consecutive ones testing, Theoretical Computer Science, 234, 59-84 (2000) · Zbl 0945.68189
[16] Hajiaghayi, M. T.; Ganjali, Y., A note on the consecutive ones submatrix problem, Information Processing Letters, 83, 163-166 (2002) · Zbl 1043.68064
[17] Hsu, W.-L., A simple test for the consecutive ones property, Journal of Algorithms, 43, 1-16 (2002) · Zbl 1050.68164
[18] Kendall, D. G., Incidence matrices, interval graphs and seriation in archaeology, Pacific Journal of Mathematics, 28, 565-570 (1969) · Zbl 0185.03301
[19] Kou, L. T., Polynomial complete consecutive information retrieval problems, SIAM Journal on Computing, 6, 67-75 (1977) · Zbl 0354.68036
[21] Oswald, M.; Reinelt, G., The weighted consecutive ones problem for a fixed number of rows or columns, Operations Research Letters, 31, 350-356 (2003) · Zbl 1033.90109
[22] Ruf, N.; Schöbel, A., Set covering with almost consecutive ones property, Discrete Optimization, 1, 215-228 (2004) · Zbl 1087.90046
[23] Tan, J.; Zhang, L., The consecutive ones submatrix problem for sparse matrices, Algorithmica, 48, 287-299 (2007) · Zbl 1121.68126
[24] Veldhorst, M., Approximation of the consecutive ones matrix augmentation problem, SIAM Journal on Computing, 14, 709-729 (1985) · Zbl 0575.68073
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.