Is there an approximation algorithm for Minimum Test Collection Problem?

Question

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 & Johnson's book.

Thanks.

Answer 1

Yes, there are approximation algorithms for this problem.

1. If $k$ is the upper bound of the test case, the authors of http://repository.cmu.edu/cgi/viewcontent.cgi?article=1397&context=tepper constructed a $O(\log{k})$-approximation algorithm
2. 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!