کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6872566 | 681651 | 2014 | 8 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Binary linear programming solutions and non-approximability for control problems in voting systems
ترجمه فارسی عنوان
راه حل های خطی باینری خطی و غیر تقریبی برای مشکلات کنترل در سیستم رای گیری
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
We show how to characterize the optimization versions of these four control problems as special digraph problems and binary linear programming formulations of linear size. Our digraph characterizations allow us to prove the hardness of approximations with absolute performance guarantee for optimal constructive control by deleting candidates in Copeland and by adding candidates in Llull voting schemes and the nonexistence of efficient approximation schemes for optimal constructive control by adding and deleting candidates in Copeland and Llull voting schemes. Our experimental study of running times using LP solvers shows that for a lot of practical instances even the hard control problems can be solved very efficiently.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 162, 10 January 2014, Pages 391-398
Journal: Discrete Applied Mathematics - Volume 162, 10 January 2014, Pages 391-398
نویسندگان
Frank Gurski, Magnus Roos,