We are given some sets $S_1, \cdots , S_n$ and two disjoint sets $A$ and $B$. A decision tree is a binary tree where each node asks "$x \in S_i? $" for some $i$, taking the left branch means "yes", taking the right branch means "no", and leaves are such that, for all $x \in A \cup B$, the answers appearing along the path from the root to the leaf imply that $x$ necessarily belongs to A or necessarily belongs to B. What is the approximation class of finding the decision tree with minimal depth?
This question was already asked in Algorithm for optimizing decision trees, but it seems that all answers given there concern constructing decision trees with minimal size (minimal number of nodes or leaves), not trees with minimal depth (e.g. Sieling'08 tackles the problem of minimizing the size).
It's very easy to AP-reduce (even S-reduce) Set Cover into this problem, so it's at least Log-APX-hard, but I couldn't find any Log approximation. May it be worse than Log-APX-hard?
