NC Algorithms for Minimum Sum of Diameters Clustering

Abstract

Given a set of n entities to be classified, and a matric of dissimilarities between pairs of them. This article 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. In sequential, Brucker showed that the problem is NP-hard, when k ≥ 3 [1]. For the case of k = 2, Hansen and Jaumard gave an O(n^3logn) algorithm [2], which Ramnath later improved the running time to O(n^3) [3]. In this article, we discuss parallel algorithms for the Minimum Sum of Diameters Clustering Problem, for the case of k = 2. In particular, we present an NC algorithm that runs in O(logn) parallel time and n^7 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, our algorithm can be implemented in O(logn) parallel time using n^6 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^3n) parallel time using n^(3.376) processors on the EREW PRAM model.