|
|
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).
|
|
|
|