کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
428547 | 686810 | 2013 | 4 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
On the hardness of finding subsets with equal average
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
• We consider ranking sets of elements based on their average utility.
• We show that deciding whether this ranking is strict is NP-hard.
• This problem originates in research on voting manipulation.
We show that, given a set of positive integers, it is NP-complete to decide whether it contains two subsets with the same average. Our interest in this problem is motivated by questions in decision theory that are related to defining preferences on sets of objects given preferences over individual objects.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 113, Issue 13, 15 July 2013, Pages 477–480
Journal: Information Processing Letters - Volume 113, Issue 13, 15 July 2013, Pages 477–480
نویسندگان
Edith Elkind, James B. Orlin,