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.