2
$\begingroup$

A real problem from the hospital.

Suppose we have $n$ blood samples to test HIV. We don't want test them one by one, since the cost is huge and most people don't have a positive result. So we try to merge them into groups, and then we just use the machine to test groups. Assume we have $k$ positive in $n$ samples, but we don't know $k$. Does a algorithm of $O(k\log_2n)$ tests (times of using the machine) exist?

  • 0
    If this is a theoretical question fine. But if this procedure is really going to be used then there are clinical standards for blood tests which must be followed. The hospital violates the approved clinical standards at its on risk. To develop a new procedure and get it approved is a massive amount of work. Immediately the point comes to mind that there must be some lower limit of detectability. So if you dilute one positive blood sample with a million clean ones then it would seem unlikely that the whole pooled sample would test positive. So how many can you mix? That is why you need an appro2012-01-29
  • 0
    @MaxW: this does not directly answer the question, so it is better as a comment.2012-08-16

1 Answers 1