1
$\begingroup$

Assume a set $S$ of elements $\{s_1,\dots,s_n\}$, each which has a hidden label 'active' or 'inactive'. Assume there are $m\ll n$ active elements in total. You are allowed to iteratively perform a single operation, which is to choose any subset $Q\subseteq S$ which returns $\mathrm{any}(Q)$ or with other words if any of the chosen elements are active. The goal is to distinguish exactly which elements are active and which are inactive. The question is if there exists an optimal policy of how to solve this in a minimal number of expected operations, either for a fixed known $m$ or for a probability distribution $p(m)$.

My first approach was to try to solve this recursively, but there was just too many ifs and special cases. By splitting in 2 until you reach an active element, discarding inactive subsets you get an algorithm that runs in $O(m\log n)$, but it is unclear whether that is optimal.

I'm looking for ideas and references as much as solutions. It just feels like there should be work that has approached this kind of problem previously.

Improve this question
$\endgroup$
5
  • 2
    $\begingroup$ Could you clarify what is the goal? Do we want merely to find an active element? Or all of them? $\endgroup$
    – Joel David Hamkins
    Commented Dec 5, 2022 at 15:49
  • 2
    $\begingroup$ But also, I am confused as to the basic set up. We are "allowed a single operation", but do you mean we can use this operation repeatedly, for different Q, or are we allowed just one use of it? Do we do the choosing of Q, or does the "operation" choose, as you seem to say? Why do you speak of a distribution for a fixed |Q|, rather than on the set of all such Q? When you refer to solving "this", what is it that is being solved exactly? Basically, I am confused about many things here. I think my understanding would benefit from an edit to the question to explain everything more carefully. $\endgroup$
    – Joel David Hamkins
    Commented Dec 5, 2022 at 16:12
  • $\begingroup$ @JoelDavidHamkins Thanks, for the comments. I have edited for clarity. $\endgroup$
    – Erik Hellsten
    Commented Dec 6, 2022 at 9:08
  • 1
    $\begingroup$ For fixed $m$, there are $\binom nm$ possible outcomes, whereas each application of your operation only gives 1 bit of information. Thus, you need at least $\log\binom nm$ operations, which is $\Omega(m\log n)$ if $m$ is much smaller than $n$ (say, $m\le n^\gamma$ for a constant $\gamma<1$). For larger $m$, this bound is about $\Omega(m\log(n/m))$. $\endgroup$
    – Emil Jeřábek
    Commented Dec 6, 2022 at 10:23
  • $\begingroup$ Also, I believe that if you count better, the “splitting in halves, discarding empty subsets” algorithm actually uses only $O(m\log(n/m))$ operations rather than $O(m\log n)$. So it is optimal up to a multiplicative constant (at least for $m\le n/2$). $\endgroup$
    – Emil Jeřábek
    Commented Dec 6, 2022 at 11:00

1 Answer 1

Reset to default
2
$\begingroup$

This problem is called group testing. The generalized binary-splitting algorithm achieves asymptotically-optimal $O(m \log (n/m))$ bound.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .