Online algorithms with advice: The tape model

ما بررسی می کنیم که چه میزان کیفیت راه حل الگوریتم های آنلاین را می توان در هنگام عرضه اطلاعات در مورد ورودی بهبود داد. برای این منظور، مفهوم اخیرا پیچیدگی مشاوره ای که در آن الگوریتم دسترسی به یک رشته مشاوره ای که توسط اوراکل با دسترسی به ورودی کامل برقرار می شود، اصلاح می شود. پیچیدگی توصیه طول این ارتباط است. ما ارتباط بین پیچیدگی مشاوره و هر دو جبرگرایی و تصادفی را با استفاده از مسئله پینگ پینگ، زمانبندی فروشگاه شغل و مشکل مسیریابی به عنوان نمونه های نمونه بررسی می کنیم. نتایج ما برای این مشکلات نشان می دهد که مشاوره بسیار کمی (فقط سه بیت در مورد صفحه بندی) به اندازه کافی بهتر از بهترین الگوریتم های قطعی است. به عنوان الگوریتم های تصادفی، تعداد کمی از بیت های مشاوره کافی است، اما با مشکل خاصی که در نظر گرفته می شود، متفاوت است. با این حال، برای به دست آوردن بهینه بودن، معمولا مشاوره بسیار ضروری است.