Finding a non-minority ball with majority answers

详细信息    查看全文

• 作者：Dá ; niel Gerbner^a ; ^{gerbner.daniel@renyi.mta.hu} ; Balá ; zs Keszegh^a ; ^{keszegh.balazs@renyi.mta.hu} ; Dö ; mö ; tö ; r Pá ; lvö ; lgyi^b ; ^{dom@cs.elte.hu} ; Balá ; zs Patkó ; s^a ; ^c ; ^{patkos.balazs@renyi.mta.hu} ; ^{patkosb@cs.elte.hu} ; Má ; té ; Vizer^a ; ^{vizer.mate@renyi.mta.hu} ; Gá ; bor Wiener^d ; ^{wiener@cs.bme.hu}
• 关键词：Combinatorial search ; Majority ; Median
• 刊名：Discrete Applied Mathematics
• 出版年：2017
• 出版时间：11 March 2017
• 年：2017
• 卷：219
• 期：Complete
• 页码：18-31
• 全文大小：489 K
• 卷排序：219

文摘

Suppose we are given a set of nn balls {b1,…,bn}{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}{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 nn balls. We show that the minimum number of queries needed to solve this problem is Θ(n)Θ(n) in the adaptive case and Θ(n3)Θ(n3) in the non-adaptive case. We also consider some related problems.