Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Approximation algorithms for a minimization variant of the order-preserving submatrices and for biclustering problems
Hochbaum D., Levin A. ACM Transactions on Algorithms9 (2):1-12,2013.Type:Article
Date Reviewed: Jun 17 2013

This well-written paper proposes two approximation algorithms for the MinOPSM problem, which is the complement of the order-preserving submatrix (OPSM) problem by Ben-Dor et al. [1]. The authors provide a 5-approximation algorithm for MinOPSM , and a 3-approximation algorithm for the dual of this optimization problem. Finally, for the biclustering problem on binary matrices, the authors propose a polynomial-time algorithm.

The problem is formulated as an optimization problem, and its similarity to set cover and partial set cover problems is used to propose approximation algorithms that are solvable in polynomial time. The theoretical foundations in this paper can lead to more accurate results in biclustering and especially in microarray experiments. This paper reduces the OPSM problem to MinOPSM, and provides polynomial-time approximation algorithms to solve it; this offers a remarkable reduction in the running time of the MinOPSM problem.

Reviewer:  Cagri Ozcaglar Review #: CR141288 (1309-0820)
1) Ben-Dor, A.; Chor, B.; Karp, R.; Yakhini, Z. Discovering local structure in gene expression data: the order-preserving submatrix problem. J. Comput. Biol. 10, 3-4(2003), 373–384.
Bookmark and Share
 
Combinatorics (G.2.1 )
 
Would you recommend this review?
yes
no
Other reviews under "Combinatorics": Date
Applied combinatorics with problem solving
Jackson B., Thoro D., Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1992. Type: Book (9780201129083)
Feb 1 1993
Parallel generation of permutations and combinations
Chen G., Chern M. BIT 26(3): 277-283, 1986. Type: Article
Jul 1 1988
Network design with non simultaneous flows
Lucertini M. (ed), Paletta G., Springer-Verlag New York, Inc., New York, NY, 1984. Type: Book (9780387818160)
Jun 1 1985
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy