On randomized algorithms for the majority problem

Demetres Christofides

Research output: Contribution to journalArticle

3 Citations (Scopus)

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 epsilon. We show that any such algorithm must have expected running time at least (2/3 - o(1)) n. 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]. (C) 2008 Elsevier B.V. All rights reserved.
Original languageEnglish
Pages (from-to)1481-1485
Number of pages5
JournalDiscrete Applied Mathematics
Volume157
Issue number7
DOIs
Publication statusPublished - 1 Apr 2009

Keywords

  • Randomized algorithms
  • Majority problem

Fingerprint

Dive into the research topics of 'On randomized algorithms for the majority problem'. Together they form a unique fingerprint.

Cite this