Simpler Logarithmic Approximation Algorithms for the Optimal Decision Tree and Adaptive Set Cover
A new greedy algorithm for identifying an unknown target hypothesis in Optimal Decision Tree problems achieves an O(log n) approximation for both average-case and worst-case costs simultaneously. This method relies on reducing the problem to Maximum Coverage, leading to a practical solution with tight cost bounds. The result is then extended to provide an O(log(k*n)) approximation for Adaptive Set Cover.