ADS 2007 - 3rd Bertinoro Workshop on Algorithms and Data Structures

September 30 - October 6, 2007
Bertinoro, Italy

Organizers:
Camil Demetrescu, University of Rome "La Sapienza", demetres@dis.uniroma1.it
Andrew Goldberg, Microsoft Research, goldberg@microsoft.com
Robert Tarjan, Princeton University, ret@cs.princeton.edu

The workshop is co-sponsored by BICI, the Bertinoro Center for Informatics, and DIMACS, the Center for Discrete Mathematics and Theoretical Computer Science.


Workshop Program:

This is a preliminary program.

Sunday, September 30, 2007

 7:30 pm       Welcome Buffet

Monday, October 1, 2007

 7:30 -  9:00  Breakfast

 9:00 -  9:10  Welcome Address

 9:10 -  9:50  Algorithm Engineering - An Attempt at a Definition
               Peter Sanders, U. Karlsruhe, Germany

 9:50 - 10:30  Route Planning in Road Networks
               Dominik Schultes, U. Karlsruhe, Germany

10:30 - 11:00  Break

11:00 - 11:40  Partitions, Metric Space Embeddings, and Distance Oracles
               Ittai Abraham, Jerusalem U., Israel

11:40 - 12:30  Geometric spanners: New Results
               Liam Roditty, Weizmann Institute, Israel

12:30 -  2:00  Lunch

 3:20 -  3:50  Tree Exploration with Logarithmic Memory
               Tomasz Radzik, King's College, London, UK

 4:00 -  4:30  Break

 4:30 -  5:00  A Survey of Algorithmic Speed Scaling
               Kirk Pruhs, U. Pittsburgh, USA

 5:10 -  5:40  Multiobjective Optimization: New Results and Applications
               Christos Zaroliagis, U. Patras, Greece

 7:30          Dinner 

Tuesday, October 2, 2007

 7:30 -  9:10  Breakfast

 9:10 -  9:50  Computing the Volume of the Union of Cubes
               Haim Kaplan, Tel-Aviv U., Israel

 9:50 - 10:30  Rectangular Layouts and Contact Graphs
               Adam Buchsbaum, AT&T Labs, USA

10:30 - 11:00  Break

11:00 - 11:40  Reach for A*: Efficient Point-to-Point Shortest Path Computation
               Renato Werneck, MSR-SVC, USA

11:40 - 12:30  SHARC: Fast and Robust Unidirectional Routing
               Daniel Delling, U. Karlsruhe, Germany

12:30 -  2:00  Lunch

 3:20 -  3:30  A Simple Streaming Problem with Applications to Power Consumption 
               in Sensor Nets (short talk)
               Valerie King, U. Victoria, Canada

 3:30 -  4:00  Distribution-Sensitive Point Location in Convex Subdivisions
               John Iacono, Polytechnic U., NYC, USA

 4:30 -  5:00  Break

 5:30 -  5:40  FPF-SB: a Scalable Algorithm for Microarray 
               Gene Expression Data Clustering
               Marco Pellegrini, IIT-CNR, Pisa, Italy

 5:40 -  6:00  Open problems session 

 7:30          Dinner 

Wednesday, October 3, 2007
 
 7:30 -  9:10  Breakfast

 9:10 -  9:50  Online Topological Ordering
               Deepak Ajwani, MPII, Germany

 9:50 - 10:30  Knowledge States: A Tool in Randomized Online Algorithms
               Wolfgang Bein, U. Nevada, Las Vegas, USA

10:30 - 11:00  Break

11:00 - 11:40  The Power of Prefix Search (with a nice open problem)
               Holger Bast, MPII, Germany

11:40 - 12:30  On the size of succinct indices
               Rajeev Raman, U. Leicester, UK

12:30 -  2:00  Lunch

Thursday, October 4, 2007
 
 7:30 -  9:10  Breakfast

 9:10 -  9:50  Interval Graph Completion and Polynomial-Time Preprocessing
               Jan Arne Telle, U. Bergen, Norway

 9:50 - 10:30  To share or not to share? An approximate answer
               Rudolf Fleischer, Fudan U., China

10:30 - 11:00  Break

11:00 - 11:40  Mergeable Trees
               Robert Tarjan, Princeton U. and HP, USA

11:40 - 12:30  Shortest Path Feasibility Algorithms: An Experimental Evaluation
               Andrew Goldberg, MSR-SVC, USA

12:30 -  2:00  Lunch

 3:20 -  4:00  Improved Dynamic Planar Point Location
               Loukas Georgiadis, HP Labs, USA

 4:00 -  4:30  Break

 4:30 -  5:00  Dictionaries: Fault Tolerance versus I/O Efficiency
               Gerth Stĝlting Brodal, U. Aarhus, Denmark

 5:00 -  5:40  Optimal Sparse Matrix Dense Vector Multiplication in the I/O-Model
               Riko Jacob, T. U. München, Germany

 7:30          Dinner 

Friday, October 5, 2007

 7:30 -  9:10  Breakfast

 9:10 -  9:50  Revisiting The Monge Property
               Mordecai Golin, Hong Kong U. Science & Technology

 9:50 - 10:30  Clustering Dynamic Data Streams
               Christian Sohler, U. Paderborn, Germany 

10:30 - 11:00  Break

11:00 - 11:40  Finding the Maximum Suffix of a String
               Torben Hagerup, U. Augsburg, Germany

11:40 - 12:20  Minimum Cycle Bases in Graphs: Algorithms and Applications
               Kurt Mehlhorn, MPII, Germany

12:20          Adjourn


Previous: Participation
Workshop Index
DIMACS Homepage
Contacting the Center
Document last modified on September 28, 2007.