NC algorithms for minimum sum of diameters clustering
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 m...
Saved in:
| Main Authors: | , |
|---|---|
| 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 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Institution: | Chiang Mai University |
| Summary: | 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. |
|---|