A Note on Clustering Aggregation for Binary Clusterings

2018/07/24 by Jiehua Chen, Danny Hermelin, Chen, Jiehua +3
Business, Management and Accounting · Computer Science · Economics, Econometrics and Finance · #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Facility Location and Emergency Management #Game Theory and Voting Systems #Optimization and Search Problems

paper · pdf · doi:10.48550/arxiv.1807.08949

openalex publication_date 2018/07/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01

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 2^o(n)⋅ |I'|^O(1)-time algorithm exists that solves any given clustering instance I' with n elements, unless the Ð fails. On the positive side, we show that the problem is fixed-parameter tractable with respect to the number of input clusterings and we give an integer linear programming formulation.

Related

• Clustering Binary Data by Application of Combinatorial Optimization Heuristics
• Clustering in Varying Metrics
• Clustering with Penalty for Joint Occurrence of Objects: Computational Aspects
• On bicluster aggregation and its benefits for enumerative solutions
• The Importance of Good Starting Solutions in the Minimum Sum of Squares Clustering Problem