# Streaming PTAS for Constrained k-Means

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Sep 2019.

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

- [A Quantum Approximation Scheme for k-Means](https://mlsanity.com/paper/2308.08167/) (2023)

## Abstract (arXiv)

We generalise the results of Bhattacharya et al. (Journal of Computing Systems, 62(1):93-115, 2018) for the list-k-means problem defined as -- for a (unknown) partition X1, ..., Xk of the dataset X subseteq ℝd, find a list of k-center sets (each element in the list is a set of k centers) such that at least one of k-center sets c1, ..., ck in the list gives an (1+varepsilon)-approximation with respect to the cost function min_textrmpermutation  π left[ sumi=1k sumx ∈ Xi ||x - cπ(i)||2 right]. The list-k-means problem is important for the constrained k-means problem since algorithms for the former can be converted to PTAS for various versions of the latter. Following are the consequences of our generalisations: - Streaming algorithm: Our D2-sampling based algorithm running in a single iteration allows us to design a 2-pass, logspace streaming algorithm for the list-k-means problem. This can be converted to a 4-pass, logspace streaming PTAS for various constrained versions of the k-means problem. - Faster PTAS under stability: Our generalisation is also useful in k-means clustering scenarios where finding good centers becomes easy once good centers for a few "bad" clusters have been chosen. One such scenario is clustering under stability where the number of such bad clusters is a constant. Using the above idea, we significantly improve the running time of the known algorithm from O(dn3) (k logn)^poly(frac1β, frac1varepsilon) to O left(dn3 k^tildeOβ varepsilon(frac1β varepsilon) right).