Finding non-minority balls with majority and plurality queries

摘要

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.

关键词