Splitting an ordering into a partition to minimize diameter

Abstract

Many algorithms can land optimal bipartitions for various objectives including minimizing the maximum cluster diameter ("min-diameter"); these algorithms are often applied iteratively in top-down fashion to derive a partition Pk consisting of k clusters, with A: > 2. Bottom-up agglomerative approaches are also commonly used to construct partitions, and we discuss these in terms of worst-case performance for metric data sets. Our main contribution derives from a new restricted partition formulation that requires each cluster to be an interval of a given ordering of the objects being clustered. Dynamic programming can optimally split such an ordering into a partition Pk for a large class of objectives that includes min-diameter. We explore a variety of ordering heuristics and show that our algorithm, when combined with an appropriate ordering heuristic, outperforms traditional algorithms on both random and non-random data sets.