A streaming algorithm for 2-center with outliers in high dimensions (Q680151)

Let \(P\) be a finite collection of points in \(d\)-dimensional Euclidean space. In the \textit{2-center problem,} one is to find two balls of minimal but equal radii that contain all of \(P\). In the outliers variant of the problem, one allows some points from \(P\) to lie outside of the two balls. Under the streaming input data assumption, where only a single pass over the set \(P\) is allowed, the authors present and establish the correctness of an approximation algorithm for solving the 2-center problem with outliers. Specifically, the algorithm produces two equal-sized balls that contain all but at most \(z\) points from \(P\) and with radius that is within a factor of \(1.8+\epsilon\) of the optimal radius. It has a \(O(d^3z^2+dz^4/\epsilon)\) space requirement, and an update time that is polynomial in \(d\), \(z\), \(1/\epsilon\) (an explicit expression is not given).