Treffer: Algorithmic and Complexity Issues of Three Clustering Methods in Microarray Data Analysis.

The complexity, approximation and algorithmic issues of several clustering problems are studied. These non-traditional clustering problems arise from recent studies in microarray data analysis. We prove the following results. (1) Two variants of the Order-Preserving Submatrix problem are NP-hard. There are polynomial-time algorithms for the Order-Preserving Submatrix Problem when the condition or gene sets are given. (2) The Smooth Subset problem cannot be approximable with ratio 0.5 +δ for any constant δ >0 unless NP=P. (3) Inferring plaid model problem is NP-hard. [ABSTRACT FROM AUTHOR]