Summary: Clustering is a common problem in the analysis of large data sets. Streaming algorithms, which make a single pass over the data set using small working memory and produce a clustering comparable in cost to the optimal offline solution, are especially useful. We develop the first streaming algorithms achieving a constant-factor approximation to the cluster radius for two variations of the \(k\)-center clustering problem. We give a streaming \((4 + \epsilon )\)-approximation algorithm using \(O(\epsilon ^{ - 1} kz)\) memory for the problem with outliers, in which the clustering is allowed to drop up to \(z\) of the input points; previous work used a random sampling approach which yields only a bicriteria approximation. We also give a streaming \((6 + \epsilon )\)-approximation algorithm using \(O(\epsilon ^{ - 1} \ln (\epsilon ^{ - 1}) k + k ^{2})\) memory for a variation motivated by anonymity considerations in which each cluster must contain at least a certain number of input points.
For the entire collection see [Zbl 1149.68010].