Majority problems of large query size

DOI10.1016/J.DAM.2018.06.015MaRDI QIDQ1720318zbMATH OpenOpenAlexWikidataFDO

Authors Dániel Gerbner, Máté Vizer

Publication date 8 February 2019

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1610.09114, http://real.mtak.hu/89776/1/1610.09114v2.pdf

zbMATH Keywords

majoritycombinatorial search

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Combinatorics in computer science (68R05) Searching and sorting (68P10)

Abstract: We study two models of the Majority problem. We are given n balls and an unknown coloring of them with two colors. We can ask sets of balls of size k as queries, and in the so-called General Model the answer to a query shows if all the balls in the set are of the same color or not. In the so-called Counting Model the answer to a query gives the difference between the cardinalities of the color classes in the query. Our goal is to show a ball of the larger color class, or prove that the color classes are of the same size, using as few queries as possible. In this paper we improve the bounds given by De Marco and Kranakis for the number of queries needed.

Recommendations

• On non-adaptive majority problems of large query size
• Computing majority via multiple queries
• Computing majority with triple queries
• On more variants of the majority problem
• Majority and plurality problems

Cites work

• Computing and Combinatorics
• Computing majority via multiple queries
• Computing majority with triple queries
• Finding a non-minority ball with majority answers
• From discrepancy to majority
• How to play the majority game with a liar
• Improved bounds and algorithms for hypergraph 2-coloring
• Majority and plurality problems
• On computing majority by comparisons
• Probabilistic strategies for the partition and plurality problems
• Randomized Algorithms for Determining the Majority on Graphs
• Randomized algorithms for finding a majority element
• Search for a majority element
• Searching for majority with \(k\)-tuple queries
• Smart elements in combinatorial group testing problems
• The plurality problem with three colors and more.
• Variants of the majority problem.

Cited in

(9)

• Adaptive majority problems for restricted query graphs and for weighted sets
• Computing majority with triple queries
• From discrepancy to majority
• A plurality problem with three colors and query size three
• On non-adaptive majority problems of large query size
• Adaptive majority problems for restricted query graphs and for weighted sets
• Searching for majority with \(k\)-tuple queries
• From discrepancy to majority
• On more variants of the majority problem

This page was built for publication: Majority problems of large query size

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1720318)