Friday, June 26, 2009 3:30 pm
-
4:30 pm
EDT (GMT -04:00)
Scheduling, Percolation, and the Worm Order
Speaker: | Peter Winkler |
---|---|
Affiliation: | Dartmouth College |
Room: | Mathematics & Computer Building (MC) 5158 |
Abstract:
We show that in any submodular system there is a maximal chain that is minimal, in a very strong sense, among all paths from 0 to 1. The consequence is a set of general conditions under which parallel scheduling can be done without backward steps. Among the applications are a fast algorithm for scheduling multiple processes without overusing a resource; a theorem about searching for a lost child in a forest; and a closed-form expression for the probability of escaping from the origin in a form of coordinate percolation.
Joint work in part with Graham Brightwell (London School of Economics) and in part with Lizz Moseman (USMA, West Point NY).