Back to Search
Start Over
The Consecutive Ones Submatrix Problem for Sparse Matrices.
- Source :
-
Algorithmica . Jul2007, Vol. 48 Issue 3, p287-299. 13p. - Publication Year :
- 2007
-
Abstract
- Abstract  A 0-1 matrix has the Consecutive Ones Property (C1P) if there is a permutation of its columns that leaves the 1's consecutive in each row. The Consecutive Ones Submatrix (C1S) problem is, given a 0-1 matrix A, to find the largest number of columns of A that form a submatrix with the C1P property. Such a problem finds application in physical mapping with hybridization data in genome sequencing. Let (a, b)-matrices be the 0-1 matrices in which there are at most a 1's in each column and at most b 1's in each row. This paper proves that the C1S problem remains NP-hard for (i) (2, 3)-matrices and (ii) (3, 2)-matrices. This solves an open problem posed in a recent paper of Hajiaghayi and Ganjali. We further prove that the C1S problem is polynomial-time 0.8-approximatable for (2, 3)-matrices in which no two columns are identical and 0.5-approximatable for (2, ∞)-matrices in general. We also show that the C1S problem is polynomial-time 0.5-approximatable for (3, 2)-matrices. However, there exists an ε > 0 such that approximating the C1S problem for (∞, 2)-matrices within a factor of nε (where n is the number of columns of the input matrix) is NP-hard. [ABSTRACT FROM AUTHOR]
- Subjects :
- *SPARSE matrices
*MATRICES (Mathematics)
*NUMERICAL analysis
*POLYNOMIALS
Subjects
Details
- Language :
- English
- ISSN :
- 01784617
- Volume :
- 48
- Issue :
- 3
- Database :
- Academic Search Index
- Journal :
- Algorithmica
- Publication Type :
- Academic Journal
- Accession number :
- 25595382
- Full Text :
- https://doi.org/10.1007/s00453-007-0118-z