کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4952365 | 1364443 | 2017 | 9 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Clustering through Continuous Facility Location Problems
ترجمه فارسی عنوان
خوشه بندی از طریق مشکلات محل سکونت تسهیلات
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
We consider the Continuous Facility Location Problem (ConFLP). Given a finite set of clients CâRd and a number fâR+, ConFLP consists in opening a set Fâ²âRd of facilities, each at cost f, and connecting each client to an open facility. The objective is to minimize the costs of opening facilities and connecting clients. We reduce ConFLP to the standard Facility Location Problem (FLP), by using the so-called approximate center sets. This reduction preserves the approximation, except for an error ε, and implies 1.488+ε and 2.04+ε-approximations when the connection cost is given by the Euclidean distance and the squared Euclidean distance, respectively. Moreover, we obtain approximate center sets for the case that the connection cost is the αth power of the Euclidean distance, achieving approximations for the corresponding problems, for any αâ¥1. As a byproduct, we also obtain a polynomial-time approximation scheme for the k-median problem with this cost function, for any fixed k.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 657, Part B, 2 January 2017, Pages 137-145
Journal: Theoretical Computer Science - Volume 657, Part B, 2 January 2017, Pages 137-145
نویسندگان
Luis A.A. Meira, Flávio K. Miyazawa, Lehilton L.C. Pedrosa,