Scheduling, Percolation, and the Worm Order
|Room:||Mathematics & Computer Building (MC) 5158|
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).
200 University Avenue West
Waterloo, ON N2L 3G1