Discrete Mathematics and Optimization Seminar
Monday, Sept. 27th, 2010
The Worm Order and its Applications
Peter Winkler
Dartmouth
Abstract: Let x and y be two words in a linearly-ordered alphabet (such as the real numbers). We say that x is below y in the worm order if they can be "scheduled" in such a way that x is always less than or equal to y.

It turns out that in any submodular system there is a maximal chain that is minimal in the worm order, among all paths from 0 to 1. One 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 (LSE) and in part with Lizz Moseman (USMA).