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.

Bonizzoni, P., DELLA VEDOVA, G., Dondi, R. (2009). A PTAS for the Minimum Consensus Clustering Problem with a Fixed Number of Clusters. In Proceedings of the 11th Italian Conference on Theoretical Computer Science (ICTCS 2009).

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

BONIZZONI, PAOLA;DELLA VEDOVA, GIANLUCA;
2009

Abstract

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.
paper
PTAS, consensus clustering
English
11th Italian Conference on Theoretical Computer Science (ICTCS 2009)
Bonizzoni, P., DELLA VEDOVA, G., Dondi, R. (2009). A PTAS for the Minimum Consensus Clustering Problem with a Fixed Number of Clusters. In Proceedings of the 11th Italian Conference on Theoretical Computer Science (ICTCS 2009).
Bonizzoni, P; DELLA VEDOVA, G; Dondi, R
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/10281/8402
Citazioni
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
Social impact