ترجمه شماره 10 - یک الگوریتم بهبود یافته برای خوشه‌بندی واحد آنلاین
سه شنبه, ۱۰ فروردين ۱۳۹۵، ۱۰:۰۶ ق.ظ
An Improved Algorithm for Online Unit Clustering
یک الگوریتم بهبود یافته برای خوشه‌بندی واحد آنلاین
فرمت ترجمه مقاله : word – قابل ویرایش
تعداد صفحات ترجمه مقاله : 12 صفحه
قیمت : 15000 تومان
چکیده
ما مسئله‌ی خوشه‌بندی واحد آنلاین که اخیراً در WAOA’06 معرفی کردیم را در یک بعد بررسی می‌کنیم: با داشتن یک دنباله از n نقطه روی خط، هدف، بخش‌بندی نقاط به حداقل تعداد زیرمجموعه‌هایی است که هر یک در یک بازه‌ی واحد قرار بگیرند. ما یک الگوریتم تصادفی‌شده‌ی آنلاین ارائه می‌کنیم که به نرخ رقابتی مورد انتظار 11/6 در مقابل حریفان فراموشکار دست می‌یابد و نرخ قبلی 15/8 را بهبود می‌بخشد. این کار، به سرعت منجر به حدود بالای بهبود یافته برای مسئله در دو بعد یا بیشتر می‌شود.
