Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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 appro –  MaxW Jan 29 '12 at 17:44
    
@MaxW: this does not directly answer the question, so it is better as a comment. –  robjohn Aug 16 '12 at 14:58

1 Answer 1

Hint: if $k=1$ a binary tree (split the samples in half, mix each half, test) works. If $k \ll n$, suppose you do a binary tree and quit testing any batch that shows negative?

share|improve this answer
    
Thanks, @Ross. k = 1 is obvious. And if k > 1, the binary tree trick might useful, but I cannot see how to get the result. The worst case is the fist k nodes are all positive? If we do it recursively, we cannot determine which step we have $T_{n/2}$ or $2T_{n/2}$ –  user22997 Jan 20 '12 at 5:34
    
@user22997: IThe worst case is the $k$ samples are paired until they all separate. One easy case is if $k=2^p$. Then you have to test all the samples until stage $p+1$, when you have $k$ trees. But if $k \ll n$ that isn't so many, so you can ignore it. In fact, it is no more than $k$. Of course, if $k=n$, you wind up testing $2n-1$ samples instead of $n$. –  Ross Millikan Jan 20 '12 at 5:40
    
Hi, @Ross: in the worst case, I got a complexity of 2k+2k($\log_2(n/k)$), it seems not O(k$\log_2n$). –  user22997 Jan 20 '12 at 23:53
    
@user22997: that is why you need $k \ll n$. If every sample is contaminated, you would have to test them all, doing $k=n$ tests. If you believe contaminated samples are rare, you will do the binary search and test twice that many. This is good if $k \lt \log_2 n$. If you have a feeling for the density of positive samples (and it is higher), you can improve this. –  Ross Millikan Jan 21 '12 at 5:42
    
it's an interesting problem. i would like to know how you use binary tree trick if k << n. –  user23744 Jan 26 '12 at 21:00

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.