Average-Case Lower Bounds for the Plurality Problem

Laurent Alonso 1 Edward M. Reingold 2
1 ALICE - Geometry and Lighting
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
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$.
Type de document :
Article dans une revue
ACM Transactions on Algorithms, Association for Computing Machinery, 2008, 4 (3), pp.27:1,27:17. 〈10.1145/1367064.1367067〉
Liste complète des métadonnées

https://hal.inria.fr/inria-00169183
Contributeur : Laurent Alonso <>
Soumis le : dimanche 2 septembre 2007 - 08:43:38
Dernière modification le : jeudi 11 janvier 2018 - 06:20:18

Identifiants

Collections

Citation

Laurent Alonso, Edward M. Reingold. Average-Case Lower Bounds for the Plurality Problem. ACM Transactions on Algorithms, Association for Computing Machinery, 2008, 4 (3), pp.27:1,27:17. 〈10.1145/1367064.1367067〉. 〈inria-00169183〉

Partager

Métriques

Consultations de la notice

202