کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
7543486 1489489 2017 19 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Buyback problem with discrete concave valuation functions
ترجمه فارسی عنوان
مشکل خرید با توابع ارزیابی مقعر گسسته
کلمات کلیدی
ترجمه چکیده
ما در مورد یک مسئله بهینه سازی دیجیتال آنلاین به نام مشکل رسیده بحث می کنیم. در ادبیات مشکل خرید، تابع ارزیابی، نشان دهنده ارزش کل عناصر انتخاب شده توسط یک تابع خطی است. در این مقاله، تعمیم مسئله بازپرداخت را با استفاده از توابع ارزیابی غیرخطی در نظر می گیریم. ما یک الگوریتم آنلاین برای مشکل با توابع ارزیابی مقعر گسسته پیشنهاد می کنیم و نشان می دهیم که آن را به نسبت رقابتی شدید، یعنی نسبت رقابت الگوریتم پیشنهاد شده برابر با معیار پایین شناخته شده برای مشکل است.
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات کنترل و بهینه سازی
پیش نمایش مقاله
مشکل خرید با توابع ارزیابی مقعر گسسته
چکیده انگلیسی
We discuss an online discrete optimization problem called the buyback problem. In the literature of the buyback problem, the valuation function representing the total value of selected elements is given by a linear function. In this paper, we consider a generalization of the buyback problem using nonlinear valuation functions. We propose an online algorithm for the problem with discrete concave valuation functions, and show that it achieves the tight competitive ratio, i.e., the competitive ratio of the proposed algorithm is equal to the known lower bound for the problem.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Optimization - Volume 26, November 2017, Pages 78-96
نویسندگان
, , ,