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)
2009
Proceedings of the 11th Italian Conference on Theoretical Computer Science (ICTCS 2009)
2009
none
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).
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: https://hdl.handle.net/10281/8402
Citazioni
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
Social impact