Sonia Cafieri, Jon Lee, et al.
Journal of Global Optimization
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.
Sonia Cafieri, Jon Lee, et al.
Journal of Global Optimization
Michael E. Henderson
International Journal of Bifurcation and Chaos in Applied Sciences and Engineering
W.C. Tang, H. Rosen, et al.
SPIE Optics, Electro-Optics, and Laser Applications in Science and Engineering 1991
Shashanka Ubaru, Lior Horesh, et al.
Journal of Biomedical Informatics