کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4949721 | 1440204 | 2017 | 14 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Finding a non-minority ball with majority answers
ترجمه فارسی عنوان
پیدا کردن توپ غیر اقلیت با پاسخ اکثریت
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
جستجوی ترکیبی اکثریت، متوسط،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
Suppose we are given a set of n balls {b1,â¦,bn} each colored either red or blue in some way unknown to us. To find out some information about the colors, we can query any triple of balls {bi1,bi2,bi3}. As an answer to such a query we obtain (the index of) a majority ball, that is, a ball whose color is the same as the color of another ball from the triple. Our goal is to find a non-minority ball, that is, a ball whose color occurs at least n2 times among the n balls. We show that the minimum number of queries needed to solve this problem is Î(n) in the adaptive case and Î(n3) in the non-adaptive case. We also consider some related problems.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 219, 11 March 2017, Pages 18-31
Journal: Discrete Applied Mathematics - Volume 219, 11 March 2017, Pages 18-31
نویسندگان
Dániel Gerbner, Balázs Keszegh, Dömötör Pálvölgyi, Balázs Patkós, Máté Vizer, Gábor Wiener,