کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
429764 | 687668 | 2007 | 25 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Approximation algorithms for spreading points
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
We consider the problem of placing n points, each one inside its own, prespecified disk, with the objective of maximizing the distance between the closest pair of them. The disks can overlap and have different sizes. The problem is NP-hard and does not admit a PTAS. In the L∞ metric, we give a 2-approximation algorithm running in time. In the L2 metric, we give a quadratic time algorithm that gives an -approximation in general, and a ∼2.2393-approximation when all the disks are congruent.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Algorithms - Volume 62, Issue 2, April 2007, Pages 49-73
Journal: Journal of Algorithms - Volume 62, Issue 2, April 2007, Pages 49-73