Events — Colloquia & Seminars
Approximating Optimal Binary Decision Trees
Speaker: Brent Heeringa, Williams College
Date: Tuesday, October 21, 2008
Talk: 12:00 PM, 366 WVH
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)
Brief Biography
Brent Heeringa is Assistant Professor of Computer Science at Williams College. He received his BA in computer science and mathematics from the University of Minnesota, Morris in 1999. He received his Ph.D. from the University of Massachusetts, Amherst in 2006. His graduate work focused on models and algorithms for improving access to organized information with applications to web site design and optimal decision making. During the final year of his graduate studies, Brent served as Vice-President of Technology for Adverplex -- a start-up company dealing primarily with pay-per-click advertising. Brent is currently working on algorithms and models for categorical data as well as approximation algorithms for reset sequences on automata.