Chen, J., Hermelin, D., & Sorge, M. (2024). A note on clustering aggregation for binary clusterings. Operations Research Letters, 52, Article 107052. https://doi.org/10.1016/j.orl.2023.11.005
E192-01 - Forschungsbereich Algorithms and Complexity
-
Journal:
Operations Research Letters
-
ISSN:
0167-6377
-
Date (published):
Jan-2024
-
Number of Pages:
6
-
Publisher:
ELSEVIER
-
Peer reviewed:
Yes
-
Keywords:
Aggregation of binary strings; Median procedure; Mirkin distance minimization; Parameterized algorithms
en
Abstract:
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)⋅|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.