Tutte seminar - Peter Winkler

Scheduling, Percolation, and the Worm Order

Abstract:

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