Get 20M+ Full-Text Papers For Less Than $1.50/day. Start a 14-Day Trial for You or Your Team.

Learn More →

Minimum sum of diameters clustering

Minimum sum of diameters clustering The problem of determining a partition of a given set ofN entities intoM clusters such that the sum of the diameters of these clusters is minimum has been studied by Brucker (1978). He proved that it is NP-complete forM≥3 and mentioned that its complexity was unknown forM=2. We provide anO(N 3 logN) algorithm for this latter case. Moreover, we show that determining a partition into two clusters which minimizes any given function of the diameters can be done inO(N 5) time. http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png Journal of Classification Springer Journals

Minimum sum of diameters clustering

Hansen, P.; Jaumard, B.
Journal of Classification , Volume 4 (2) – Jun 18, 2005
Download PDF
12 pages

Loading next page...
 
/lp/springer-journals/minimum-sum-of-diameters-clustering-hvziwbECAJ

References (14)

Publisher
Springer Journals
Copyright
Copyright © 1987 by Springer-Verlag
Subject
Statistics; Statistical Theory and Methods; Pattern Recognition; Bioinformatics; Signal,Image and Speech Processing; Psychometrics; Marketing
ISSN
0176-4268
eISSN
1432-1343
DOI
10.1007/BF01896987
Publisher site
See Article on Publisher Site

Abstract

The problem of determining a partition of a given set ofN entities intoM clusters such that the sum of the diameters of these clusters is minimum has been studied by Brucker (1978). He proved that it is NP-complete forM≥3 and mentioned that its complexity was unknown forM=2. We provide anO(N 3 logN) algorithm for this latter case. Moreover, we show that determining a partition into two clusters which minimizes any given function of the diameters can be done inO(N 5) time.

Journal

Journal of Classification – Springer Journals

Published: Jun 18, 2005

There are no references for this article.