1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ I imagine that Garey and Johnson reduced 3DM to (not from) MTC, since only this direction establishes the NP-completeness of MTC. $\endgroup$ Oct 28, 2017 at 13:19

1 Answer 1

1
$\begingroup$

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!

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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