Rounds in a combinatorial search problem
Not on the map. Why?
Abstract (arXiv)
We consider the following combinatorial search problem: we are given some excellent elements of [n] and we should find at least one, asking questions of the following type: "Is there an excellent element in A subset [n]?". G.O.H. Katona proved sharp results for the number of questions needed to ask in the adaptive, non-adaptive and two-round versions of this problem. We verify a conjecture of Katona by proving that in the r-round version we need to ask rn1/r+O(1) queries for fixed r and this is sharp. We also prove bounds for the queries needed to ask if we want to find at least d excellent elements.
Key facts. Cited by 1 paper in the map (data through 14 Oct 2026). First posted on arXiv 30 Nov 2016.
Builds on
No reference list yet.
Built on by
Citing papers per year: 2023: 1.
1 paper.
- 2023On Detecting Some Defective Items in Group Testingcited by 0
- 2023On Detecting Some Defective Items in Group Testing27 Jun 2023