Groupe d’études et de recherche en analyse des décisions

G-96-28

Polynomial Algorithms for Nested Univariate Clustering

, et

Clique partitionning in Euclidean space Rn consists in finding a partition of a given set of N points into M clusters in order to minimize the sum of within-cluster interpoint distances. For n = 1 clusters need not consist of consecutive points on a line but have a nestedness property. Exploiting this property, an O (N5 M2) dynamic programming algorithm is proposed. A (N) algorithm is also given for the case M = 2.

, 15 pages

Ce cahier a été révisé en novembre 2000