|
Friday, June 26, 2009 |
|
|
|
|
Scheduling, Percolation, and the Worm Order |
|
|
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. |