کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
434461 689739 2013 24 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Better bounds on online unit clustering
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Better bounds on online unit clustering
چکیده انگلیسی

Unit clustering is the problem of dividing a set of points from a metric space into a minimal number of subsets such that the points in each subset are enclosable by a unit ball. We continue the work, recently initiated by Chan and Zarrabi-Zadeh, on determining the competitive ratio of the online version of this problem. For the one-dimensional case, we develop a deterministic algorithm, improving the best known upper bound of 7/4 by Epstein and van Stee to 5/3. This narrows the gap to the best known lower bound of 8/5 to only 1/15. Our algorithm automatically leads to improvements in all higher dimensions as well. Finally, we strengthen the deterministic lower bound in two dimensions and higher from 2 to 13/6.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 500, 19 August 2013, Pages 1–24
نویسندگان
, ,