On randomized algorithms for the majority problem |
| |
Authors: | Demetres Christofides |
| |
Affiliation: | School of Mathematics, University of Birmingham, Birmingham B15 2TT, United Kingdom |
| |
Abstract: | In the majority problem, we are given n balls coloured black or white and we are allowed to query whether two balls have the same colour or not. The goal is to find a ball of majority colour in the minimum number of queries. The answer is known to be n−B(n) where B(n) is the number of 1’s in the binary representation of n. In this paper we study randomized algorithms for determining majority, which are allowed to err with probability at most ε. We show that any such algorithm must have expected running time at least . Moreover, we provide a randomized algorithm which shows that this result is best possible. These extend a result of De Marco and Pelc [G. De Marco, A. Pelc, Randomized algorithms for determining the majority on graphs, Combin. Probab. Comput. 15 (2006) 823-834]. |
| |
Keywords: | Randomized algorithms Majority problem |
本文献已被 ScienceDirect 等数据库收录! |
|