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.