Algorithmic and Complezity Issues of Three Clustering Methods in Microarray Data Analysis (Eztended Abstract)

摘要：

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 OrderPreserving Subma-trix 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.

作者: Jinsong Tan Kok Seng Chua Louxin Zhang

作者单位: Department of Mathematics National University of Singapore, Singapore 117543 The Inst. of High Performance Computing Singapore 117528

会议类型: 国际会议

会议名称: The 11th Annual International Computing and Combinatorics Conference COCOON 2005(第11届国际计算和组合会议)

会议地点: 昆明

会议语种:英文

页码: 74-83

在线出版日期: 2005-08-01（万方平台首次上网日期，不代表论文的发表时间）