On the parallel complexity of minimum sum of diameters clustering

Given a set of n entities to be classified, and a matric of dissimilarities between pairs of them. This paper considers the problem called Minimum Sum of Diameters Clustering Problem, where a partition of the set of entities into k clusters such that the sum of the diameters of these clusters is minimized. Brucker showed that the complexity of the problem is NP-hard, when k ≥ 3 [1]. For the case of k = 2, Hansen and Jaumard gave an O(n³ log n) algorithm [2], which Ramnath later improved the running time to O(n³) [3]. This paper discusses the parallel complexity of the Minimum Sum of Diameters Clustering Problem. For the case of k = 2, we show that the problem in parallel in fact belongs in class NC¹ In particular, we show that the parallel complexity of the problem is O(log n) parallel time and n⁷ processors on the Common CRCW PRAM model. Additionally, we propose the parallel algorithmic technique which can be applied to improve the processor bound by a factor of n. As a result, we show that the problem can be quickly solved in O(log n) parallel time using n⁶ processors on the Common CRCW PRAM model. In addition, regarding the issue of high processor complexity, we also propose a more practical NC algorithm which can be implemented in O(log³ n) parallel time using n^3.376 processors on the EREW PRAM model.