Conference Proceedings

A Polynomial Time Approximation Scheme for k-Consensus Clustering

Tom Coleman, Anthony Wirth

PROCEEDINGS OF THE TWENTY-FIRST ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS | SIAM | Published : 2010

Abstract

This paper introduces a polynomial time approximation scheme for the metric CORRELATION CLUSTERING problem, when the number of clusters returned is bounded (by k). CONSENSUS CLUSTERING is a fundamental aggregation problem, with considerable application, and it is analysed here as a metric variant of the CORRELATION CLUSTERING problem. The PTAS exploits a connection between CORRELATION CLUSTERING and the k-CUT problems. This requires the introduction of a new rebalancing technique, based on minimum cost perfect matchings, to provide clusters of the required sizes. Both CONSENSUS CLUSTERING and CORRELATION CLUSTERING have been the focus of considerable recent study. There is an existing dichot..

View full abstract