Scheduling, Percolation, and the Worm Order

  • Date: 04/19/2007

Peter Winkler (Dartmouth College)


University of Washington


When can you schedule a multi-step process without having to take
backward steps? Critical are an old concept called "submodularity", a
new structure called the "worm order", and a variation of what
physicists call "percolation". With these tools we will attempt to
update the computer system
at UW, find a lost child in the Cascades, and minimize water usage in Seattle, all without backward steps.

Joint work in part with Graham Brightwell (LSE) and in part with Lizz
Moseman (Dartmouth). (This talk is designed to be accessible to
undergraduates interested in mathematics.)

Other Information: 

10th Anniversary Speaker Series 2007