January 14, 2004
Astor Crowne Plaza Hotel, New Orleans, LA
Online
Registration Form
Poster
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 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
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
Agenda |
Wednesday
Jan 14 |
8:30 am |
Welcome and Introduction |
8:40-10:15 |
SESSION I
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-12:00 |
SESSION II
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 |
SESSION III
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-5:15 |
SESSION IV
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.