John R. Kender, Rick Kjeldsen
IEEE Transactions on Pattern Analysis and Machine Intelligence
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.
John R. Kender, Rick Kjeldsen
IEEE Transactions on Pattern Analysis and Machine Intelligence
William Hinsberg, Joy Cheng, et al.
SPIE Advanced Lithography 2010
Jianke Yang, Robin Walters, et al.
ICML 2023
F.M. Schellenberg, M. Levenson, et al.
BACUS Symposium on Photomask Technology and Management 1991