Majority and Plurality Problems

Details Majority and Plurality Problems Majority and Plurality Problems

2012-03-07

arxiv.org/abs/1203.1398v1

Mathematics

Combinatorics

Scientific paper

Given a set of n balls each colored with a color, a ball is said to be majority, k-majority, plurality if its color class has size larger than half of the number of balls, has size at least k, has size larger than any other color class; respectively. We address the problem of finding the minimum number of queries (a comparison of a pair of balls if they have the same color or not) that is needed to decide whether a majority, k-majority or plurality ball exists and if so then show one such ball. We consider both adaptive and non-adaptive strategies and in certain cases, we also address weighted versions of the problems.

Affiliated with

Also associated with

No associations

Rating

Majority and Plurality Problems does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Majority and Plurality Problems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Majority and Plurality Problems will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-393470