No-substitution k-means Clustering with Adversarial Order

Robi Bhattacharjee, Michal Moshkovitz

We investigate $k$-means clustering in the online no-substitution setting when the input arrives in \emph{arbitrary} order. In this setting, points arrive one after another, and th…