A Fast and Effective Method for Euclidean Anticlustering: The Assignment-Based-Anticlustering Algorithm
P. Baumann, O. Goldschmidt, D. S. Hochbaum, J. Yang · 2026
Read A Fast and Effective Method for Euclidean Anticlustering: The Assignment-Based-Anticlustering Algorithm by P. Baumann, O. Goldschmidt, D. S. Hochbaum, J. Yang (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-06351.txt.
Description
Grouping items so each group mirrors the whole set is the opposite of clustering, and it is computationally hard. Philipp Baumann and 3 co-authors present a fast algorithm for Euclidean anticlustering in a 2026 paper. Objects in the same anticluster should be as dissimilar as possible, making each group representative of everything.
Applications include social studies, cross-validation, and forming mini-batches for machine learning, where datasets reach millions of items. Their Assignment-Based Anticlustering algorithm scales to millions of objects and hundreds of thousands of groups within seconds to minutes, far beyond earlier methods. An extensive computational study showed better solutions in less time than existing approaches, including for categorized data. On the related balanced graph partitioning problem, it also beat the well-known METIS method.
Catalog record
| CREATOR | P. Baumann, O. Goldschmidt, D. S. Hochbaum, J. Yang |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 95 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2601-06351