کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4952432 | 1442031 | 2016 | 11 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Approximate composable truthful mechanism design
ترجمه فارسی عنوان
تقریبا سازنده درست طراحی مکانیسم
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
طراحی مکانیسم، حراج کوله پشتی، الگوریتم های تقریبی،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
This paper aims to study techniques for designing truthful mechanisms for a combinatorial optimization problem that might require composition algorithms. We show that the composition algorithm AâB is monotone if the algorithm A and the algorithm B are both monotone. We apply this technique to the two-dimensional orthogonal knapsack problem with provable constant approximation bounds, improving the previous non-constant results in [5]. Moreover, we show that the technique can also be applied to the heterogeneous multiple clusters scheduling problem, and a truthful mechanism with provable approximation bounds was presented.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 654, 22 November 2016, Pages 188-198
Journal: Theoretical Computer Science - Volume 654, 22 November 2016, Pages 188-198
نویسندگان
Deshi Ye, Guochuan Zhang,