3526 articles – 5249 references  [version française]

inria-00169183, version 1

## Average-Case Lower Bounds for the Plurality Problem

Laurent Alonso () a1, Edward M. Reingold b2

ACM Transactions on Algorithms 4, 3 (2008) 27:1,27:17

Abstract: Given a set of $n$ elements, each of which is colored one of $c \geq 2$ colors, we have to determine an element of the plurality (most frequently occurring) color by pairwise equal/unequal color comparisons of elements. We derive lower bounds for the expected number of color comparisons when the $c^n$ colorings are equally probable. We prove a general lower bound of $\frac{c}{3} n - O( \sqrt n)$ for $c \geq 2$; we prove the stronger particular bounds of $\frac{7}{6} n - O(\sqrt n)$ for $c=3$, $\frac{54}{35} n - O(\sqrt n)$ for $c = 4$, $\frac{607}{315}n-O(\sqrt n)$ for $c=5$, $\frac{1592}{693}n - O(\sqrt n)$ for $c = 6$, $\frac{7985}{3003} n - O(\sqrt n)$ for $c = 7$, and $\frac{19402}{6435} n - O(\sqrt n)$ for $c = 8$.

• a –  INRIA
• b –  Illinois Institute of Technology, Chicago
• 1:  ALICE (INRIA Lorraine - LORIA)
• INRIA – CNRS : UMR7503 – Université Henri Poincaré - Nancy I – Université Nancy II – Institut National Polytechnique de Lorraine (INPL)
• 2:  Department of Computer Science [IIT] (IIT CS)
• Illinois Institute of Technology
• Domain : Computer Science/Data Structures and Algorithms

• inria-00169183, version 1
• oai:hal.inria.fr:inria-00169183
• From:
• Submitted on: Sunday, 2 September 2007 08:43:38
• Updated on: Thursday, 25 September 2008 16:21:18