A stochastic algorithm for online bipartite resource allocation problems

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