A randomized PTAS for the minimum consensus clustering with a fixed number of clusters

DOI10.1016/J.TCS.2011.12.022MaRDI QIDQ418755zbMATH OpenOpenAlexFDO

Authors Paola Bonizzoni, Gianluca Della Vedova, Riccardo Dondi

Publication date 30 May 2012

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2011.12.022

Mathematics Subject Classification ID

Pattern recognition, speech recognition (68T10) Randomized algorithms (68W20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Recommendations

• On the parameterized complexity of consensus clustering
• On the parameterized complexity of consensus clustering
• scientific article; zbMATH DE number 6297742
• A randomized algorithm for estimating the number of clusters
• Approximation algorithms for min-sum \(p\)-clustering
• On constructing an optimal consensus clustering from multiple clusterings
• PTAS for \(p\)-means \(q\)-medoids \(r\)-given clustering problem
• A unified framework of FPT approximation algorithms for clustering problems
• A simple \(D ^{2}\)-sampling based PTAS for \(k\)-means and other clustering problems
• A PTAS for k-means clustering based on weak coresets

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 6297742 (Why is no real title available?)
• A cutting plane algorithm for a clustering problem
• Aggregating inconsistent information: ranking and clustering
• Algorithms - ESA 2003
• Approximate solution of NP optimization problems
• Approximation schemes for clustering problems
• Clustering with qualitative information
• Correlation clustering
• Correlation clustering with a fixed number of clusters
• Correlation clustering with partial information
• Correlation clustering, maximizing agreements via semidefinite programming
• Data Integration in the Life Sciences
• Linear time approximation schemes for the Gale-Berlekamp game and related minimization problems
• NP-hard problems in hierarchical-tree clustering
• On the approximation of correlation clustering and consensus clustering
• Optimization, approximation, and complexity classes
• The complexity of computing medians of relations.

Cited in

(7)

• Parameterized algorithms for min-max 2-cluster editing
• Approximation Algorithms for Biclustering Problems
• On the parameterized complexity of consensus clustering
• On the parameterized complexity of consensus clustering
• On constructing an optimal consensus clustering from multiple clusterings
• Combinatorial Pattern Matching
• Minimum adjusted Rand index for two clusterings of a given size

This page was built for publication: A randomized PTAS for the minimum consensus clustering with a fixed number of clusters

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q418755)