A dynamic learning algorithm for online matching problems with concave returns

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