Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4949140 | Computational Geometry | 2017 | 11 Pages |
Abstract
We study the 2-center problem with outliers in high-dimensional data streams. Given a stream of points in arbitrary d dimensions, the goal is to find two congruent balls of minimum radius covering all but at most z points. We present a (1.8+ε)-approximation streaming algorithm, improving over the previous (4+ε)-approximation algorithm available for the problem. The space complexity and update time of our algorithm are poly(d,z,1/ε), independent of the size of the stream.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Behnam Hatami, Hamid Zarrabi-Zadeh,