Scheduling, Percolation, and the Worm Order

Scheduling, Percolation, and the Worm Order

-
Peter Winkler, Darthmouth College
Fine Hall 224

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 (LSE) and in part with Lizz Moseman (USMA).