# A Unified Framework for Clustering Constrained Data without Locality Property

arXiv: https://arxiv.org/abs/1810.01049 · HTML: https://mlsanity.com/paper/1810.01049/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Oct 2018.

## Built on by (most cited first, 7 of 7)

- [Tight FPT Approximation for Socially Fair Clustering](https://mlsanity.com/paper/2106.06755/) (2021)
- [Parameterized Approximation Schemes for Clustering with General Norm Objectives](https://mlsanity.com/paper/2304.03146/) (2023)
- [Tight FPT Approximation for Constrained k-Center and k-Supplier](https://mlsanity.com/paper/2110.14242/) (2021)
- [Coresets for constrained k-median and k-means clustering in low dimensional Euclidean space](https://mlsanity.com/paper/2106.07319/) (2021)
- [Relax and Merge: A Simple Yet Effective Framework for Solving Fair k-Means and k-sparse Wasserstein Barycenter Problems](https://mlsanity.com/paper/2411.01115/) (2024)
- [Universal Weak Coreset](https://mlsanity.com/paper/2305.16890/) (2023)
- [A Sub-4 Approximation for Fair k-Means](https://mlsanity.com/paper/2609.07974/) (2026)

## Abstract (arXiv)

In this paper, we consider a class of constrained clustering problems of points in ℝd, where d could be rather high. A common feature of these problems is that their optimal clusterings no longer have the locality property (due to the additional constraints), which is a key property required by many algorithms for their unconstrained counterparts. To overcome the difficulty caused by the loss of locality, we present in this paper a unified framework, called em Peeling-and-Enclosing (PnE), to iteratively solve two variants of the constrained clustering problems, em constrained k-means clustering (k-CMeans) and em constrained k-median clustering (k-CMedian). Our framework is based on two standalone geometric techniques, called em Simplex Lemma and em Weaker Simplex Lemma, for k-CMeans and k-CMedian, respectively. The simplex lemma (or weaker simplex lemma) enables us to efficiently approximate the mean (or median) point of an unknown set of points by searching a small-size grid, independent of the dimensionality of the space, in a simplex (or the surrounding region of a simplex), and thus can be used to handle high dimensional data. If k and frac1ε are fixed numbers, our framework generates, in nearly linear time (em i.e., O(n(log n)k+1d)), O((log n)k) k-tuple candidates for the k mean or median points, and one of them induces a (1+ε)-approximation for k-CMeans or k-CMedian, where n is the number of points. Combining this unified framework with a problem-specific selection algorithm (which determines the best k-tuple candidate), we obtain a (1+ε)-approximation for each of the constrained clustering problems. We expect that our technique will be applicable to other constrained clustering problems without locality.