کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
5128282 | 1378587 | 2016 | 16 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
An approximation algorithm for the Euclidean incremental median problem
ترجمه فارسی عنوان
یک الگوریتم تقریبی برای مسئله متوسط مداخله اقلیدسی
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
میانه های افزایشی، میانی اقلیدسی، خوشه بندی سلسله مراتبی، الگوریتم تقریبی، الگوریتم آنلاین،
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
کنترل و بهینه سازی
چکیده انگلیسی
In the incremental version of the k-median problem, we find a sequence of facility sets F1âF2ââ¯âFn, where each Fk contains at most k facilities. This sequence is said to be δ-competitive if the cost of each Fk is at most δ times the optimum cost of k facilities. The best deterministic (randomized) algorithm available for the metric space has a competitive ratio of 8 (7.656). The best one for the one-dimensional problem finds a 5.828-competitive sequence. We give a 7.076-competitive solution for the high-dimensional Euclidean space.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Optimization - Volume 22, Part B, November 2016, Pages 312-327
Journal: Discrete Optimization - Volume 22, Part B, November 2016, Pages 312-327
نویسندگان
Vladimir Shenmaier,