Organizing Committee: Guy Blelloch, Daniel Sleator, Robert Tarjan

Dynamic algorithms maintain various properties of a system as its inputs are dynamically modified. If the modifications are slight, then updating a property by making use of previous work can be much more efficient than computing it from scratch. Over the past twenty years the understanding of the design and analysis of dynamic algorithms has increased dramatically, and efficient solutions have been found for a wide variety of problems. Examples include maintaining the minimum-spanning-tree of a graph as edges are added or deleted, and maintaining the convex hull of a set of points as points are added, deleted or moved.

One would assume that dynamic algorithms would be very useful in "real world" applications. Data in such applications often changes over time: internet links go down, web pages get added, roads are detoured, employees call in sick, loose screws delay flights, and robots need to deal with moving obstacles. To date, however, the application of dynamic algorithms has been limited.

The purpose of this PROBE is to bring together researchers in dynamic algorithms with potential users. The goals include (1) better understanding in what applications dynamic algorithms are likely to be most useful, (2) better understanding the state-of-the art in the design and performance of dynamic algorithms for various problems, (3) and considering new problems for which dynamic algorithms should be studied.