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

الگوریتم های آنلاین با مشاوره: مدل نوار

عنوان انگلیسی
Online algorithms with advice: The tape model
کد مقاله سال انتشار تعداد صفحات مقاله انگلیسی
105618 2017 25 صفحه PDF
منبع

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

Journal : Information and Computation, Volume 254, Part 1, June 2017, Pages 59-83

ترجمه کلمات کلیدی
پیچیدگی مشاوره، محاسبات آنلاین، تحلیل رقابتی، پیمایش تخصیص مسیر متقابل جدول زمانبندی کار،
کلمات کلیدی انگلیسی
Advice complexity; Online computation; Competitive analysis; Paging; Disjoint path allocation; Job shop scheduling;
ترجمه چکیده
ما بررسی می کنیم که چه میزان کیفیت راه حل الگوریتم های آنلاین را می توان در هنگام عرضه اطلاعات در مورد ورودی بهبود داد. برای این منظور، مفهوم اخیرا پیچیدگی مشاوره ای که در آن الگوریتم دسترسی به یک رشته مشاوره ای که توسط اوراکل با دسترسی به ورودی کامل برقرار می شود، اصلاح می شود. پیچیدگی توصیه طول این ارتباط است. ما ارتباط بین پیچیدگی مشاوره و هر دو جبرگرایی و تصادفی را با استفاده از مسئله پینگ پینگ، زمانبندی فروشگاه شغل و مشکل مسیریابی به عنوان نمونه های نمونه بررسی می کنیم. نتایج ما برای این مشکلات نشان می دهد که مشاوره بسیار کمی (فقط سه بیت در مورد صفحه بندی) به اندازه کافی بهتر از بهترین الگوریتم های قطعی است. به عنوان الگوریتم های تصادفی، تعداد کمی از بیت های مشاوره کافی است، اما با مشکل خاصی که در نظر گرفته می شود، متفاوت است. با این حال، برای به دست آوردن بهینه بودن، معمولا مشاوره بسیار ضروری است.
پیش نمایش مقاله
پیش نمایش مقاله  الگوریتم های آنلاین با مشاوره: مدل نوار

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

We investigate to what extent the solution quality of online algorithms can be improved when supplying them with information about the input. To this end, we refine the recently introduced notion of advice complexity where the algorithm has access to an advice string that is communicated by an oracle with access to the complete input. The advice complexity is the length of this communication. We study the connections between advice complexity and both determinism and randomization using the paging problem, job shop scheduling, and a routing problem as sample problems. Our results for these problems show that very small advice (only three bits in the case of paging) suffices to significantly improve over the best deterministic algorithms. To be as good as randomized algorithms, a moderate number of advice bits is sufficient, but it varies with the specific problem considered. However, to obtain optimality, usually very large advice is necessary.