On the parameterized complexity of consensus clustering

DOI10.1016/J.TCS.2014.05.002MaRDI QIDQ2015135zbMATH OpenOpenAlexFDO

Authors Martin Dörnfelder, Jiong Guo, Christian Komusiewicz, Mathias Weller

Publication date 23 June 2014

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

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

zbMATH Keywords

local searchNP-hard problemdata clusteringsearch tree algorithm

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• On the parameterized complexity of consensus clustering
• A randomized PTAS for the minimum consensus clustering with a fixed number of clusters
• On constructing an optimal consensus clustering from multiple clusterings
• Algorithms and Computation
• On the approximation of correlation clustering and consensus clustering

Cites work

• scientific article; zbMATH DE number 1082099 (Why is no real title available?)
• scientific article; zbMATH DE number 1161563 (Why is no real title available?)
• scientific article; zbMATH DE number 6297742 (Why is no real title available?)
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• 10.1162/153244303321897735
• A randomized PTAS for the minimum consensus clustering with a fixed number of clusters
• Advances in \(k\)-means clustering. A data mining thinking.
• Average parameterization and partial kernelization for computing medians
• Cluster graph modification problems
• Consensus clustering: A resampling-based method for class discovery and visualization of gene expression microarray data
• Correlation clustering
• Fundamentals of parameterized complexity
• Incremental list coloring of graphs, parameterized by conservation
• Linear time approximation schemes for the Gale-Berlekamp game and related minimization problems
• Local search: is brute-force avoidable?
• NP-hard problems in hierarchical-tree clustering
• On Local Search and Placement of Meters in Networks
• On the approximation of correlation clustering and consensus clustering
• On the hardness of losing weight
• Parametrized complexity theory.
• Searching the \(k\)-change neighborhood for TSP is W[1]-hard
• Stable assignment with couples: parameterized complexity and local search
• The complexity of computing medians of relations.
• The parameterized complexity of local search for TSP, more refined
• Theoretical aspects of local search.

Cited in

(13)

• Parameterized Algorithmics for Graph Modification Problems: On Interactions with Heuristics
• On the parameterized complexity of consensus clustering
• A note on clustering aggregation for binary clusterings
• On constructing an optimal consensus clustering from multiple clusterings
• scientific article; zbMATH DE number 7525465 (Why is no real title available?)
• Cluster Editing in Multi-Layer and Temporal Graphs.
• A randomized PTAS for the minimum consensus clustering with a fixed number of clusters
• A Biclustering Framework for Consensus Problems
• On the convergence of puck clustering systems
• scientific article; zbMATH DE number 6297742 (Why is no real title available?)
• Clustering and isolation in the consensus problem for partitions
• Parameterized \(k\)-clustering: tractability island
• Cluster editing for multi-layer and temporal graphs

This page was built for publication: On the parameterized complexity of consensus clustering

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