Please use this identifier to cite or link to this item: http://scholarbank.nus.edu.sg/handle/10635/102875
Title: Approximation algorithms for the consecutive ones submatrix problem on sparse matrices
Authors: Tan, J.
Zhang, L. 
Issue Date: 2004
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 [12]. 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)
URI: http://scholarbank.nus.edu.sg/handle/10635/102875
ISSN: 03029743
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

Page view(s)

43
checked on Oct 26, 2018

Google ScholarTM

Check


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.