Approximating Optimal Binary Decision Trees

Monday, November 23, 2009

Presenter: Brent Heeringa
Affiliation: Williams College
Time: 11:15 - 12:15
Location: EE/CS 3-125
Schedule:View Extended Schedule Details

Abstract

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 = (T1 , . . . , Tm) and a set of n items X = (X1 , . . . , Xn ). 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 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.

(joint work with Micah Adler)

Bio

Brent Heeringa is an Assistant Professor of Computer Science at Williams College where he teaches courses on algorithms, complexity, and theory of computation. Brent received his Ph.D. from the University of Massachusetts, Amherst in 2006. His graduate work focused on models and methods for improving access to organized information with applications to optimal decision making and website design. He received a B.A. with highest distinction in mathematics and computer science from the University of Minnesota, Morris in 1999. During his final year of graduate studies, Brent helped several other computer scientists start Adverplex -- a company dealing primarily with pay-per-click advertising. Brent is presently on sabbatical at Boston University where he is a visiting scholar. His current research focuses on approximation algorithms and data structures.