کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4949140 | 1439986 | 2017 | 11 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
A streaming algorithm for 2-center with outliers in high dimensions
ترجمه فارسی عنوان
الگوریتم جریان برای مرکز 2 با خروجی ها در ابعاد بزرگ
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
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.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computational Geometry - Volume 60, January 2017, Pages 26-36
Journal: Computational Geometry - Volume 60, January 2017, Pages 26-36
نویسندگان
Behnam Hatami, Hamid Zarrabi-Zadeh,