A PTAS for the Minimum Consensus Clustering Problem with a Fixed Number of Clusters

Details A PTAS for the Minimum Consensus Clustering Problem with a Fixed Number of Clusters A PTAS for the Minimum Consensus Clustering Problem with a Fixed Number of Clusters

2009-07-10

arxiv.org/abs/0907.1840v1

Computer Science

Data Structures and Algorithms

Scientific paper

The Consensus Clustering problem has been introduced as an effective way to analyze the results of different microarray experiments. The problem consists of looking for a partition that best summarizes a set of input partitions (each corresponding to a different microarray experiment) under a simple and intuitive cost function. The problem admits polynomial time algorithms on two input partitions, but is APX-hard on three input partitions. We investigate the restriction of Consensus Clustering when the output partition is required to contain at most k sets, giving a polynomial time approximation scheme (PTAS) while proving the NP-hardness of this restriction.

Affiliated with

Also associated with

No associations

Rating

A PTAS for the Minimum Consensus Clustering Problem with a Fixed Number of Clusters does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A PTAS for the Minimum Consensus Clustering Problem with a Fixed Number of Clusters, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A PTAS for the Minimum Consensus Clustering Problem with a Fixed Number of Clusters will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-164837