<div class="csl-bib-body">
<div class="csl-entry">Chen, J., Hermelin, D., & Sorge, M. (2024). A note on clustering aggregation for binary clusterings. <i>Operations Research Letters</i>, <i>52</i>, Article 107052. https://doi.org/10.1016/j.orl.2023.11.005</div>
</div>
-
dc.identifier.issn
0167-6377
-
dc.identifier.uri
http://hdl.handle.net/20.500.12708/208035
-
dc.description.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.
en
dc.language.iso
en
-
dc.publisher
ELSEVIER
-
dc.relation.ispartof
Operations Research Letters
-
dc.subject
Aggregation of binary strings
en
dc.subject
Median procedure
en
dc.subject
Mirkin distance minimization
en
dc.subject
Parameterized algorithms
en
dc.title
A note on clustering aggregation for binary clusterings
