Coresets for Weight-Constrained Anisotropic Assignment and Clustering

Abstract We construct small coresets for weight-constrained anisotropic assignment and clustering with a specific view toward applications in materials science. Building on previous results for unconstrained least-squares clustering of Har-Peled & Kushal, we obtain coresets even for weight-constrained anisotropic clustering and, particularly, reduce the dependence of their sizes on the number of clusters from cubic to quadratic, an improvement which is decisive for applications in small dimensions such as grain mapping.