Back

G-89-29

Weight Constrained Maximum Split Clustering

, , and

BibTeX reference

Consider N entities to be classified, with given weights, and a matrix of dissimilarities between pairs of them. The split of a cluster is the smallest dissimilarity between an entity in this cluster and an entity outside it. The single-linkage algorithm provides partitions into M clusters for which the smallest split is maximum. We consider the problems of finding maximum split partitions with exactly M clusters and with at most M clusters subject to the additional constraint that the sum of the weights of the entities in each cluster never exceeds a given bound. These two problems are shown to be NP-hard and reducible to a sequence of bin-packing problems. A (N 2) algorithm for the particular case M=N of the second problem is also presented. Computational experience is reported.

, 28 pages

This cahier was revised in June 1990