A sextic algorithm for building optimal websites
Brent Heeringa
University of Massachusetts
October 21, 2004
12:40 pm - 1:40pm
NWSE N201
Abstract

I introduce the Constrained Subtree Selection (CSS) problem as a model for designing optimal websites. CSS takes as input a set of web pages, some organization of the web pages, and the popularity of the web pages. It returns a website which doesn't violate the semantics of the original organization and for which the average search time for a page is minimized. After a gentle review of dynamic programming, I will describe and analyze an O(n^6) dynamic programming algorithm for instances of CSS where the prior organization does not constrain the choice of website.

Lunch will be provided in Steinmetz 237 at noon. After the talk, Mr. Heeringa will return to room 237 for an open discussion with students.