3532 articles – 5253 Notices  [english version]

inria-00169184, version 1

Determining Plurality

Laurent Alonso () 1, Edward M. Reingold a, 2

ACM Transactions on Algorithms 4, 3 (2008) 26:1,26:19

Résumé : Given a set of $n$ elements, each of which is colored one of $c$ colors, we must determine an element of the plurality (most frequently occurring) color by pairwise equal/unequal color comparisons of elements. We prove that $(c-1)(n-c)/2$ color comparisons are necessary in the worst case to determine the plurality color and give an algorithm requiring $(0.775 c + 5.9)n + O(c^2)$ color comparisons for $c \geq 9$.

  • a –  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
  • Domaine : Informatique/Algorithme et structure de données
 
  • inria-00169184, version 1
  • http://hal.inria.fr/inria-00169184
  • oai:hal.inria.fr:inria-00169184
  • Contributeur : Laurent Alonso <>
  • Soumis le : Dimanche 2 Septembre 2007, 09:04:28
  • Dernière modification le : Jeudi 25 Septembre 2008, 16:18:17