کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
436361 | 689994 | 2014 | 12 صفحه PDF | دانلود رایگان |
Given a collection CC of partitions of a base set S, the NP-hard Consensus Clustering problem asks for a partition of S which has a total Mirkin distance of at most t to the partitions in CC, where t is a nonnegative integer. We present a parameterized algorithm for Consensus Clustering with running time O(4.24k⋅k3+|C|⋅|S|2)O(4.24k⋅k3+|C|⋅|S|2), where k:=t/|C|k:=t/|C| is the average Mirkin distance of the solution partition to the partitions of CC. Furthermore, we strengthen previous hardness results for Consensus Clustering, showing that Consensus Clustering remains NP-hard even when all input partitions contain at most two subsets. Finally, we study a local search variant of Consensus Clustering, showing W[1]-hardness for the parameter “radius of the Mirkin-distance neighborhood”. In the process, we also consider a local search variant of the related Cluster Editing problem, showing W[1]-hardness for the parameter “radius of the edge modification neighborhood”.
Journal: Theoretical Computer Science - Volume 542, 3 July 2014, Pages 71–82