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