Is there an approximation algorithm for Minimum Test Collection Problem? The problem is defined as follows:

Instance: A finite set $A$ of "possible diagnoses," a collection $C$ of subsets of $A$, representing binary "tests," and a positive integer $J≤|C|$.

Question: Is there a subcollection $C′⊆ C$ with $|C′|≤ J$ such that, for every pair $a_{i},a_{j}$ of possible diagnoses from $A$, there is some test $c∈C′$ for which $|{a_{i},a_{j}}|∩ c|=1$ (that is, a test $c$ that "distinguishes" between $a_{i}$ and $a_{j}$)?

And we know that MTC is $NP$-complete, it has been proved by reducing it to 3 Dimensional Matching problem in the Garey &amp; Johnson's book.

Thanks.
Yes, there are approximation algorithms for this problem. 


If $k$ is the upper bound of the test case, the authors of http://repository.cmu.edu/cgi/viewcontent.cgi?article=1397&amp;context=tepper
constructed a $O(\log{k})$-approximation algorithm
Another approximation algorithm of the same complexity is derived here: 
https://link.springer.com/chapter/10.1007/3-540-44676-1_13


Hope that helps!