Simpler Logarithmic Approximation Algorithms for the Optimal Decision Tree and Adaptive Set Cover

We study the problem of constructing a decision tree that identifies an unknown hypothesis from a given ground set, under both average- and worst-case cost. The Optimal Decision Tree (ODT) problem has been extensively studied in the literature, and O(n) -approximation guarantees are known for each criterion, including a simultaneous guarantee for both (here n is the number of hypotheses) [ICML]. Although most of the existing algorithm use simple greedy strategies, their analyses rely on intricate arguments. Since ODT is a fundamental problem with wide-ranging applications, we are interested in developing algorithms that are both effective and easy to understand. We present a new greedy algorithm with a simplified analysis that simultaneously achieves approximation factors below 3.65 2 n for worst-case cost and 7.3 2 n for average-case cost. Our algorithm for the Optimal Decision Tree behaves greedily with respect to the hereby introduced Separating Subfamily problem which asks for the cheapest subfamily of tests which partitions the hypotheses into pieces of small enough size. We show that the Separating Subfamily can itself be reduced to an instance of the well-known Maximum Coverage problem. At the core of our approach lies exploiting properties of cutting a clique into small pieces, where edges represent pairs of hypotheses to be separated. In the spirit of simplicity, we also provide a new and straightforward application of ODT: an O((k times n)) -approximation for the Adaptive Set Cover problem, where k is the number of possible realizations.