科研之友
微信
新浪微博
Facebook
分享链接
摘要
Given a set of n colored balls, a majority, non-minority or plurality ball is one whose color class has size more than n/2, at least n/2 or larger than any other color class, respectively. We describe linear time algorithms for finding non-minority balls using query sets of size q of the following form: the answer to a majority/plurality query Q is a majority/plurality ball in Q or the statement that there is no such ball in Q.
