On the approximation of correlation clustering and consensus clustering

DOI10.1016/j.jcss.2007.06.024zbMath1169.68586OpenAlexW2028356989WikidataQ59444453 ScholiaQ59444453MaRDI QIDQ931713

Gianluca Della Vedova, Paola Bonizzoni, Riccardo Dondi, Tao Jiang

Publication date: 26 June 2008

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2007.06.024

zbMATH Keywords

approximationPTASAPX-hardnesscorrelation clusteringconsensus clustering

Mathematics Subject Classification ID

Pattern recognition, speech recognition (68T10) Data structures (68P05) Approximation algorithms (68W25)

Related Items

PathOGiST: A Novel Method for Clustering Pathogen Isolates by Combining Multiple Genotyping Signals, Parameterized algorithms for min-max 2-cluster editing, A randomized PTAS for the minimum consensus clustering with a fixed number of clusters, Parameterized algorithms for the 2-clustering problem with minimum sum and minimum sum of squares objective functions, On Geometric Prototype and Applications, Cost-optimal constrained correlation clustering via weighted partial maximum satisfiability, On the parameterized complexity of consensus clustering, Average parameterization and partial kernelization for computing medians, A literature review on correlation clustering: cross-disciplinary taxonomy with bibliometric analysis

Cites Work

• Correlation clustering
• NP-hard problems in hierarchical-tree clustering
• A cutting plane algorithm for a clustering problem
• Polynomial time approximation schemes for dense instances of \( \mathcal{NP}\)-hard problems
• Some APX-completeness results for cubic graphs
• A new rounding procedure for the assignment problem with applications to dense graph arrangement problems
• Clustering with qualitative information
• A Polynomial Time Approximation Scheme for Inferring Evolutionary Trees from Quartet Topologies and Its Application
• Algorithms on Strings, Trees and Sequences
• Data Integration in the Life Sciences
• Algorithms - ESA 2003
• Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques
• Aggregating inconsistent information
• Unnamed Item
• Unnamed Item
• Unnamed Item