This workshop will be held immediately following
Symposium on Discrete Algorithms (SODA04) being held January
Dynamic algorithms maintain properties of a system as its inputs
are dynamically modified. If the modifications are slight, updating
a property can be much more efficient than computing it from scratch.
Over the past twenty years the understanding of dynamic algorithms
has increased dramatically, and efficient dynamic solutions have
been developed 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.
Dynamic algorithms should be very useful in many "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, flights are delayed, and robots need to
deal with moving obstacles. To date, however, the application
of dynamic algorithms has been limited--updates are often made
in batches at infrequent intervals.
The purpose of this workshop is to bring together researchers
in dynamic algorithms with potential users. The goals include
(1) better understanding in what applications dynamic algorithms
are currently used, (2) better understanding in what applications
dynamic algorithms are likely to be most useful, (3) better understanding
the state-of-the art in the design and performance of dynamic
algorithms for various problems, and (4) studying new problems
for which dynamic algorithms should be studied.
The workshop will contain both invited and contributed presentations.
Anyone interested in presenting should send a title and brief
abstract to Guy
by October 31. Because the workshop is only one day, any contributed
talks will be limited to 10 minutes. Anyone is welcome to attend
the workshop and participate in discussion.
Carnegie Mellon University
King, University of
Carnegie Mellon University
E. Tarjan, Princeton
Registration is required. (Registration for this workshop will be separate from registration
for SODA04. To register for SODA04, please visit http://www.siam.org/meetings/da04/.) There is a fee for attending this workshop, with a discount
available for attendees who preregister by Monday, January 5, 2004. Your registration fee includes:
- Admission to all workshop sessions.
- Continental breakfast, lunch, and morning and afternoon
*Students must provide proof of current enrollment
in the form of a current valid student ID or a signed letter from
their faculty advisor.
registration (after 1/5/04)
|All funds are in US dollars.
||Welcome and Introduction
Guibas (Stanford University)
What is new with Kinetic Data Structures?
Agarwal (Duke University)
Indexing moving objects (pdf)
Kuffner (Carnegie Mellon University)
Self-Collision detection and motion planning for humanoid
|10:15 - 10:40
F. Italiano (Universita di Roma)
Engineering dynamic graph algorithms:
a round trip between theory and experiments
Demetrescu (Universita di Roma)
Recent developments in dynamic path problems
B. Powell (Princeton University)
Approximate dynamic programming methods for dynamic resource
|12:00 - 1:30
|1:30 - 3:10
Demaine (MIT), John
Iacono (Polytechnic U.) and
Stefan Langerman (Universite
Libre de Bruxelles)
Retroactive data structures (pdf)
Acar (Carnegie Mellon University)
Self-adjusting computation (ppt)
Reps (University of Wisconsin)
Finite differencing of logical formulas for static analysis
Thorup (AT&T Labs)
Using dynamic shortest paths in a local search minimizing
Werneck (Princeton University)
A direct implementation of top trees
Roditty (Tel Aviv University)
A fully dynamic reachability algorithm for directed graphs
with an almost linear update time. (ppt)
Future Directions for Dynamic and Kinetic Problems
This workshop is being sponsored
by the ALADDIN
Center, an NSF-funded collaboration among Carnegie Mellon
University, Princeton University, and industrial partners.