کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
437614 | 690164 | 2015 | 11 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
One-dimensional k-center on uncertain data
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
Problems on uncertain data have attracted significant attention due to the imprecise nature of many measurement data. In this paper, we consider the k -center problem on one-dimensional uncertain data. The input is a set PP of (weighted) uncertain points on a real line, and each uncertain point is specified by its probability density function (pdf) which is a piecewise-uniform function (i.e., a histogram). The goal is to find a set Q of k points on the line to minimize the maximum expected distance from the uncertain points of PP to their expected closest points in Q. We present efficient algorithms for this uncertain k-center problem and their running times almost match those for the “deterministic” k-center problem.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 602, 18 October 2015, Pages 114–124
Journal: Theoretical Computer Science - Volume 602, 18 October 2015, Pages 114–124
نویسندگان
Haitao Wang, Jingru Zhang,