On the parameterized complexity of consensus clustering

DOI10.1016/j.tcs.2014.05.002zbMath1360.68506MaRDI QIDQ2015135

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

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

68Q25: Analysis of algorithms and problem complexity

68T20: Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

Related Items

Unnamed Item, Cluster Editing in Multi-Layer and Temporal Graphs., Parameterized Algorithmics for Graph Modification Problems: On Interactions with Heuristics

Cites Work

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