کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4950740 | 1440715 | 2016 | 25 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Prices matter for the parameterized complexity of shift bribery
ترجمه فارسی عنوان
قیمت مواد برای پیچیدگی پارامتریک رشوه خواری
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
In the Shift Bribery problem, we are given an election, a preferred candidate p, and a budget. The goal is to ensure p's victory by shifting p higher in some voters' preference orders. However, each such shift request comes at a price and we must not exceed the given budget. We study the parameterized computational complexity of Shift Bribery for a number of parameters and several classes of price functions: For the number of affected voters, Shift Bribery is W[2]-hard for Borda, Maximin, and Copeland. For the number of positions by which p is shifted in total, the problem is fixed-parameter tractable for Borda and Maximin, and is W[1]-hard for Copeland. For the budget, the results depend on the price function class. Finally, Shift Bribery tends to be tractable when parameterized by the number of voters, but the results for the number of candidates are more enigmatic.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information and Computation - Volume 251, December 2016, Pages 140-164
Journal: Information and Computation - Volume 251, December 2016, Pages 140-164
نویسندگان
Robert Bredereck, Jiehua Chen, Piotr Faliszewski, André Nichterlein, Rolf Niedermeier,