caa a22 4500 46575029X CHVBK 20180323111832.0 cr unu---uuuuu 170327e19900901xx s 000 0 eng 10.1007/BF01908717 doi (NATIONALLICENCE)springer-10.1007/BF01908717 Weight constrained maximum split clustering [Elektronische Daten] [P. Hansen, B. Jaumard, K. Musitu] ConsiderN 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 that cluster and an entity outside it. The single-linkage algorithm provides partitions intoM clusters for which the smallest split is maximum. We consider the problems of finding maximum split partitions with exactlyM clusters and with at mostM 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 caseM =N of the second problem is also presented. Computational experience is reported. Springer-Verlag New York Inc., 1990 Partition nationallicence Single-linkage nationallicence Split nationallicence Cluster weight nationallicence Constrained clustering nationallicence Hansen P. Rutgers Center for Operations Research, Hill Center for the Mathematical Sciences, Rutgers University, 08903, New Brunswick, New Jersey, USA aut Jaumard B. GERAD and Département de Mathématiques Appliquées, Ecole Polytechnique, Campus de l'Université de Montréal, Succursale "A”, Case Postale 6079, H3C 3A7, Montréal, Québec, Canada aut Musitu K. GERAD and McGill University, Montréal aut Journal of Classification Springer-Verlag 7/2(1990-09-01), 217-240 0176-4268 7:2<217 1990 7 357 https://doi.org/10.1007/BF01908717 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/BF01908717 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Hansen P. Rutgers Center for Operations Research, Hill Center for the Mathematical Sciences, Rutgers University, 08903, New Brunswick, New Jersey, USA aut NATIONALLICENCE 700 1- Jaumard B. GERAD and Département de Mathématiques Appliquées, Ecole Polytechnique, Campus de l'Université de Montréal, Succursale "A”, Case Postale 6079, H3C 3A7, Montréal, Québec, Canada aut NATIONALLICENCE 700 1- Musitu K. GERAD and McGill University, Montréal aut NATIONALLICENCE 773 0- Journal of Classification Springer-Verlag 7/2(1990-09-01), 217-240 0176-4268 7:2<217 1990 7 357 Metadata rights reserved Springer special CC-BY-NC licence nationallicence SWISSBIB 46575029X BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer