Minimum sum of diameters clustering |
| |
Authors: | P Hansen B Jaumard |
| |
Institution: | (1) Rutgers Center for Operations Research, Rutgers University, 08903 New Brunswick, NJ, USA;(2) Computer Aids for Industrial Productivity, Hill Center for the Mathematical Sciences, Rutgers University, 08903 New Brunswick, NJ, USA |
| |
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 forM3 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.Acknowledgments: This research was supported by the Air Force Office of Scientific Research Grant AFOSR 0271 to Rutgers University. We are grateful to Yves Crama for several insightful remarks and to an anonymous referee for detailed comments. |
| |
Keywords: | Partition Diameter Complexity Polynomial algorithm Divisive hierarchical clustering |
本文献已被 SpringerLink 等数据库收录! |
|