Swarthmore College Department of Computer Science

Talk by Brent Heeringa, University of Massachusetts

Approximating Optimal Binary Decision Trees
Thursday, February 23 2006
4:30pm in Science Center 240

Abstract

Decision trees have a rich history in computer science with applications ranging from medical diagnosis to experiment design. An instance of Decision Tree (DT) is a set of m binary tests T= (T_1, ..., T_m) and a set of n items X=(X_1, ..., 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. The total external path length of the tree is the sum of the depths of all the leaves in the tree. In this talk, I give a (ln n + 1)-approximation for the Decision Tree problem. I also show that DT does not have a PTAS unless P=NP. This work, while providing the first non-trivial upper and lower bounds on approximating DT, also demonstrates that DT and a subtly different problem which also bears the name decision tree, have fundamentally different approximation complexity.