دانلود مقاله ISI انگلیسی شماره 47188
عنوان فارسی مقاله

یک استراتژی رقابتی برای تخصیص شکل آنلاین با فاصله آگاهانه

کد مقاله سال انتشار مقاله انگلیسی ترجمه فارسی تعداد کلمات
47188 2014 12 صفحه PDF سفارش دهید محاسبه نشده
خرید مقاله
پس از پرداخت، فوراً می توانید مقاله را دانلود فرمایید.
عنوان انگلیسی
A competitive strategy for distance-aware online shape allocation
منبع

Publisher : Elsevier - Science Direct (الزویر - ساینس دایرکت)

Journal : Theoretical Computer Science, Volume 555, 23 October 2014, Pages 43–54

کلمات کلیدی
خوشه - میانگین فاصله - مشکلات آنلاین - شکل مطلوب یک شهرستان - تحلیل رقابتی
پیش نمایش مقاله
پیش نمایش مقاله یک استراتژی رقابتی برای تخصیص شکل آنلاین با فاصله آگاهانه

چکیده انگلیسی

We consider the following online allocation problem: Given a unit square S  , and a sequence of numbers ni∈[0,1]ni∈[0,1] with ∑j=0inj⩽1; at each step i  , select a region CiCi of previously unassigned area nini in S  . The objective is to make these regions compact in a distance-aware sense: minimize the maximum (normalized) average Manhattan distance between points from the same set CiCi. Related location problems have received a considerable amount of attention; in particular, the problem of determining the “optimal shape of a city”, i.e., allocating a single  nini has been studied. We present an online strategy, based on an analysis of space-filling curves; for continuous shapes, we prove a factor of 1.8092, and 1.7848 for discrete point sets.

خرید مقاله
پس از پرداخت، فوراً می توانید مقاله را دانلود فرمایید.