کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6874239 | 1441031 | 2018 | 5 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Balanced allocation through random walk
ترجمه فارسی عنوان
تخصیص متعادل از طریق پیاده روی تصادفی
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
تخصیص متعادل پیاده روی تصادفی، هش کردن قاچ، الگوریتم های آنلاین،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
We consider the allocation problem in which mâ¤(1âε)dn items are to be allocated to n bins with capacity d. The items x1,x2,â¦,xm arrive sequentially and when item xi arrives it is given two possible bin locations pi=h1(xi),qi=h2(xi) via hash functions h1,h2. We consider a random walk procedure for inserting items and show that the expected time insertion time is constant provided ε=Ω(logâ¡dd).
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 131, March 2018, Pages 39-43
Journal: Information Processing Letters - Volume 131, March 2018, Pages 39-43
نویسندگان
Alan Frieze, Samantha Petti,