CENTER Carnegie Mellon UniversityCarnegie Mellon Computer Science DepartmentSchool of Computer Science
Workshop on Dynamic Algorithms and Applications
Related Activities
Outreach Roadshow

January 14, 2004
Astor Crowne Plaza Hotel, New Orleans, LA

Online Registration Form

This workshop will be held immediately following the ACM-SIAM Symposium on Discrete Algorithms (SODA04) being held January 11-13, 2004.

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

Organizing committee:
Guy Blelloch, Carnegie Mellon University
Valerie King, University of Victoria, Canada
Daniel Sleator, Carnegie Mellon University
Robert E. Tarjan, Princeton University
Mikkel Thorup, AT&T Labs-Research

Registration and Payment Information

Registration is required. (Registration for this workshop will be separate from registration for SODA04. To register for SODA04, please visit 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 coffee breaks.

  Regular Student*
Pre-registration (by 1/5/04)
$20 free
On-site registration (after 1/5/04) $40 $20
All funds are in US dollars.
  *Students must provide proof of current enrollment in the form of a current valid student ID or a signed letter from their faculty advisor.

Online Registration Form

Wednesday Jan 14
8:30 am Welcome and Introduction


8:40 Leo Guibas (Stanford University)
What is new with Kinetic Data Structures?

9:25 Pankaj Agarwal (Duke University)
Indexing moving objects (pdf)

9:50 James Kuffner (Carnegie Mellon University)
Self-Collision detection and motion planning for humanoid robots (pdf)

10:15 - 10:40 Break


10:40 Giuseppe F. Italiano (Universita di Roma)
Engineering dynamic graph algorithms:
a round trip between theory and experiments

11:10 Camil Demetrescu (Universita di Roma)
Recent developments in dynamic path problems

11:35 Warren B. Powell (Princeton University)
Approximate dynamic programming methods for dynamic resource
allocation problems

12:00 - 1:30 Lunch
1:30 - 3:10


1:30 Erik Demaine (MIT), John Iacono (Polytechnic U.) and
Stefan Langerman (Universite Libre de Bruxelles)
Retroactive data structures (pdf)

1:55 Umut Acar (Carnegie Mellon University)
Self-adjusting computation (ppt)

2:20 Thomas Reps (University of Wisconsin)
Finite differencing of logical formulas for static analysis (ppt), (pdf)

2:45 Mikkel Thorup (AT&T Labs)
Using dynamic shortest paths in a local search minimizing
Internet congestion

3:10-3:35 Break


3:35 Renato Werneck (Princeton University)
A direct implementation of top trees

3:55 Liam Roditty (Tel Aviv University)
A fully dynamic reachability algorithm for directed graphs
with an almost linear update time. (ppt)

4:15 Panel Discussion
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.



This material is based upon work supported by National Science Foundation under Grant No. 0122581.
Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the
National Science Foundation