An Optimization Algorithm for Cluster Analysis,

Given a set of N points and distances between all points, the paper presents an algorithm for determining an optimal partition of the points into k mutually exclusive and exhaustive subsets or clusters according to an objective function defined on the set of all partitions. The value of the objective function for a given partition is defined as the maximum within-cluster distance in the partition. The algorithm determines an optimal partition by solving a sequence of set-covering problems. The set-covering problems have no more than N constraints and typically less than 1.5N variables. Author