Approximating Optimal Binary Decision Trees

We give a (ln n+1)-approximation for the decision tree (DT) problem. An instance of DT is a set of m binary tests T=(T (1),aEuro broken vertical bar,T (m) ) and a set of n items X=(X (1),aEuro broken vertical bar,X (n) ). The goal is to output a binary tree where each internal node is a test, each leaf is an item and the total external path length of the tree is minimized. Total external path length is the sum of the depths of all the leaves in the tree. DT has a long history in computer science with applications ranging from medical diagnosis to experiment design. It also generalizes the problem of finding optimal average-case search strategies in partially ordered sets which includes several alphabetic tree problems. Our work decreases the previous best upper bound on the approximation ratio by a constant factor. We provide a new analysis of the greedy algorithm that uses a simple accounting scheme to spread the cost of a tree among pairs of items split at a particular node. We conclude by showing that our upper bound also holds for the DT problem with weighted tests.