کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
434005 | 689668 | 2015 | 8 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Efficient algorithms for the one-dimensional k-center problem
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
We consider the problem of finding k centers for n weighted points on a real line. This (weighted) k -center problem was solved in O(nlogn)O(nlogn) time previously by using Cole's parametric search and other complicated approaches. In this paper, we present an easier O(nlogn)O(nlogn) time algorithm that avoids the parametric search, and in certain special cases our algorithm solves the problem in O(n)O(n) time. In addition, our techniques involve developing interesting data structures for processing queries that find a lowest point in the common intersection of a certain subset of half-planes. This subproblem is interesting in its own right and our solution for it may find other applications as well.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 592, 9 August 2015, Pages 135–142
Journal: Theoretical Computer Science - Volume 592, 9 August 2015, Pages 135–142
نویسندگان
Danny Z. Chen, Jian Li, Haitao Wang,