Open Access Open Access  Restricted Access Subscription Access

NC Algorithms for Minimum Sum of Diameters Clustering

Nopadon Juneam,
Sanpawat Kantabutra,

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.

Keywords


NC algorithm; PRAM algorithm; Clustering; Minimum sum of diameters

Citation Format:
Nopadon Juneam, Sanpawat Kantabutra, "NC Algorithms for Minimum Sum of Diameters Clustering," Journal of Internet Technology, vol. 18, no. 4 , pp. 899-905, Jul. 2017.

Full Text:

PDF

Refbacks

  • There are currently no refbacks.





Published by Executive Committee, Taiwan Academic Network, Ministry of Education, Taipei, Taiwan, R.O.C
JIT Editorial Office, Library and Information Center, National Dong Hwa University
No. 1, Sec. 2, Da Hsueh Rd. Shoufeng, Hualien 97401, Taiwan, R.O.C.
Tel: +886-3-931-7017  E-mail: jit.editorial@gmail.com