Gerbner, Dániel and Katona, Gyula and Pálvölgyi, Dömötör and Patkós, Balázs (2013) Majority and plurality problems. DISCRETE APPLIED MATHEMATICS, 161 (6). pp. 813-818. ISSN 0166-218X
![]() |
Text
gyulla13.pdf Restricted to Registered users only Download (137kB) | Request a copy |
Abstract
Given a set of n balls each colored with a color, a ball is said to be a majority, k-majority, or plurality ball if its color class has size larger than half of the number of balls, has size at least k, or has size larger than any other color class, respectively. We address the problem of finding the minimum number of queries (comparisons of a pair of balls as regards whether they have the same color or not) needed to decide whether a majority, k-majority or plurality ball exists and, if it does, then to show one such ball. We consider both adaptive and non-adaptive strategies and, for certain cases, we also address weighted versions of the problems. © 2012 Elsevier B.V. All rights reserved.
Item Type: | Article |
---|---|
Uncontrolled Keywords: | Plurality; Majority; Combinatorial search; COLOR; Mathematical techniques; Combinatorial mathematics; Plurality problems |
Subjects: | Q Science / természettudomány > QA Mathematics / matematika |
SWORD Depositor: | MTMT SWORD |
Depositing User: | MTMT SWORD |
Date Deposited: | 10 Dec 2013 19:58 |
Last Modified: | 10 Dec 2013 19:58 |
URI: | http://real.mtak.hu/id/eprint/7985 |
Actions (login required)
![]() |
Edit Item |