A Parallel Branch-and-Bound Method for Cluster Analysis

UNCG Author/Contributor (non-UNCG co-authors, if there are any, appear on document)
Lakshmi S. Iyer, Associate Professor (Creator)
Institution
The University of North Carolina at Greensboro (UNCG )
Web Site: http://library.uncg.edu/

Abstract: Cluster analysis is a generic term coined for procedures that are used objectively to group entities based on their similarities and differences. The primary objective of these procedures is to group n items into K mutually exclusive clusters so that items within each cluster are relatively homogeneous in nature while the clusters themselves are distinct. In this research, we have developed, implemented and tested an asynchronous, dynamic parallel branchand-bound algorithm to solve the clustering problem. In the developmental environment, several processes (tasks) work independently on various subproblems generated by the branch-and-bound procedure. This parallel algorithm can solve very large-scale, optimal clustering problems in a reasonable amount of wall-clock time. Linear and superlinear speedups are obtained. Thus, solutions to real-world, complex clustering problems, which could not be solved due to the lack of efficient parallel algorithms, can now be attempted.

Additional Information

Publication
Annals of Operations Research
Language: English
Date: 1999
Keywords
integer programming, combinatorial optimization, parallel optimization, cluster analysis

Email this document to