کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6896363 | 1445995 | 2015 | 10 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
A dynamic learning algorithm for online matching problems with concave returns
ترجمه فارسی عنوان
یک الگوریتم یادگیری پویا برای مشکلات تطبیق آنلاین با بازده مقعر
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
ترجمه چکیده
ما یک مشکل تطبیق آنلاین با بازدهی مقعر را در نظر می گیریم. این مشکل تعمیمی از مشکل تطبیق آنلاین سنتی است و برنامه های گسترده ای در تبلیغات آنلاین دارد. در این کار، ما یک الگوریتم یادگیری پویا ارائه می دهیم که عملکرد نزدیک به مطلوب را برای این مشکل به دست می آورد زمانی که ورودی ها به صورت تصادفی وارد می شوند و شرایط خاصی را برآورده می کنند. ایده کلیدی الگوریتم ما این است که الگوی داده ورودی را به صورت پویا یاد بگیریم: ما یک دنباله ای از مشکلات اختصاصی اختصاص یافته جزئی را حل می کنیم و از راه حل های بهینه آنها برای حل تصمیم های آینده استفاده می کنیم. تحلیل ما متعلق به پارادایم اولیه دوگانه است؛ با این حال، عدم وجود خطی بودن تابع هدف و ویژگی پویای الگوریتم، تجزیه و تحلیل ما را کاملا منحصر به فرد می کند. ما همچنین از طریق آزمایش های عددی نشان می دهیم که الگوریتم ما برای داده های آزمون خوب عمل می کند.
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
علوم کامپیوتر (عمومی)
چکیده انگلیسی
We consider an online matching problem with concave returns. This problem is a generalization of the traditional online matching problem and has vast applications in online advertising. In this work, we propose a dynamic learning algorithm that achieves near-optimal performance for this problem when the inputs arrive in a random order and satisfy certain conditions. The key idea of our algorithm is to learn the input data pattern dynamically: we solve a sequence of carefully chosen partial allocation problems and use their optimal solutions to assist with the future decisions. Our analysis belongs to the primal-dual paradigm; however, the absence of linearity of the objective function and the dynamic feature of the algorithm makes our analysis quite unique. We also show through numerical experiments that our algorithm performs well for test data.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Operational Research - Volume 247, Issue 2, 1 December 2015, Pages 379-388
Journal: European Journal of Operational Research - Volume 247, Issue 2, 1 December 2015, Pages 379-388
نویسندگان
Xiao Alison Chen, Zizhuo Wang,