کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
9657774 | 690375 | 2005 | 15 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
On the approximability of the range assignment problem on radio networks in presence of selfish agents
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
We investigate the existence of payment schemes which induce the stations to follow the decisions of a network manager in computing a range assignment, that is, truthful mechanisms for the range assignment problem. We provide both positive and negative results on the existence of truthful VCG-based mechanisms for this NP-hard problem. We prove that (i) in general, every polynomial-time truthful VCG-based mechanism computes a solution of cost far-off the optimum, unless P=NP and (ii) there exists a polynomial-time truthful VCG-based mechanism achieving constant approximation for practically relevant, still NP-hard versions, i.e., the metric and the well-spread case.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 343, Issues 1â2, 10 October 2005, Pages 27-41
Journal: Theoretical Computer Science - Volume 343, Issues 1â2, 10 October 2005, Pages 27-41
نویسندگان
Christoph Ambühl, Andrea E.F. Clementi, Paolo Penna, Gianluca Rossi, Riccardo Silvestri,