We consider the clustering aggregation problem in which we are given a set of clusterings and want to find an aggregated clustering which minimizes the sum of mismatches to the input clusterings. In the binary case (e...
详细信息
We consider the clustering aggregation problem in which we are given a set of clusterings and want to find an aggregated clustering which minimizes the sum of mismatches to the input clusterings. In the binary case (each clustering is a bipartition) this problem was known to be NP-hard under Turing reductions. We strengthen this result by providing a polynomial-time many-one reduction. Our result also implies that no 2o(n)center dot |I'|O(1)-time algorithm exists that solves any given clustering instance I' with n elements, unless the Exponential Time Hypothesis fails. On the positive side, we show that the problem is fixed-parameter tractable with respect to the number of input clusterings.(c) 2023 Elsevier B.V. All rights reserved.
暂无评论