[Colloq] REMINDER: Today - Colloquium Talk - Brent Heeringa, Tuesday, Oct. 21

[Rachel Kalweit]

Brent Heeringa will be giving at talk on Tuesday Oct. 21 at 12:00 in room 366 West Village H.

Title: Approximating Optimal Binary Decision Trees

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 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.

Host: Rajmohan Rajaraman