Please use this identifier to cite or link to this item:
|Title:||Approximation algorithms for the consecutive ones submatrix problem on sparse matrices|
|Citation:||Tan, J.,Zhang, L. (2004). Approximation algorithms for the consecutive ones submatrix problem on sparse matrices. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 3341 : 835-846. ScholarBank@NUS Repository.|
|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 (COS) 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 has potential applications in physical mapping with hybridization data. This paper proves that the COS problem remains NP-hard for i) (2, 3)-matrices with at most two 1's in each column and at most three 1's in each row and for ii) (3, 2)-matrices with at most three 1's in each column and at most two 1's in each row. This solves an open problem posed in a recent paper of Hajiaghayi and Ganjali . We further prove that the COS problem is 0.8-approximatable for (2, 3)-matrices and 0.5-approximatable for the matrices in which each column contains at most two 1's and for (3,2)-matrices. © Springer-Verlag 2004.|
|Source Title:||Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)|
|Appears in Collections:||Staff Publications|
Show full item record
Files in This Item:
There are no files associated with this item.
checked on Oct 26, 2018
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.