NC algorithms for minimum sum of diameters clustering

• Main Authors: Juneam N., Kantabutra S.
• Format: Journal
• Published: 2017
• Online Access: https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85028464135&origin=inward; http://cmuir.cmu.ac.th/jspui/handle/6653943832/40906
• Institution: Chiang Mai University

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 κ clusters such that the sum of the diameters of these clusters is minimized. In sequential, Brucker showed that the problem is NP-hard, when κ ≥ 3 [1]. For the case of κ = 2, Hansen and Jaumard gave an O(n 3 logn) 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 κ = 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 3 n) parallel time using n 3.376 processors on the EREW PRAM model.