[Colloq] Colloquium Talk - Brent Heeringa, Tuesday, Oct. 21
Rachel Kalweit
rachelb at ccs.neu.edu
Fri Oct 10 16:37:23 EDT 2008
Brent Heeringa will be giving at talk on Tuesday Oct. 21 at 11am 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
Rachel M. Kalweit
College of Computer and Information Science
202 West Village H
Northeastern University
phone: 617-373-2462
fax: 617-373-5121
rachelb at ccs.neu.edu
More information about the Colloq
mailing list