|
You can also
download the program as a PDF file 
INVITED SPEAKERS
Ricardo Baeza-Yates
Yahoo! Research Barcelona (Barcelona, Spain)
| TITLE: |
|
Algorithmic Challenges in Web Search Engines |
| ABSTRACT: |
|
We present the main algorithmic challenges that large Web
search engines face today. These challenges are present in all the modules
of a Web retrieval system, ranging from the gathering of the data to be
indexed (crawling) to the selection and ordering of the answers to a query
(searching and ranking). Most of the challenges are ultimately related to
the quality of the answer or the efficiency in obtaining it, although some are
relevant even to the existence of current search engines: context based
advertising.
As the Web grows and changes at a fast pace, the algorithms behind these
challenges must rely in large scale experimentation, both in data volume and
computation time, to understand the main issues that affect them. We show
examples of our own research and of the state of the art.
|
Jon Bentley
Avaya Labs Research (Basking Ridge, NJ, USA)
| TITLE: |
|
Little Experiments for Algorithms and Life |
| ABSTRACT: |
|
Algorithmic experiments come in all sizes. A jumbo testbed for the
Traveling Salesman Problem, for instance, can take years to build, and
additional years can be spent designing and running insightful
experiments. This talk concentrates on tiny algorithmic experiments
that can be conducted in a few minutes. Such experiments include
parameter estimation, hypothesis testing, determining functional
forms, and conducting horse races. This talk also describes
how tiny Math, Science and Engineering (MSE) can be done in
one's head or on the back of the proverbial envelope, and shows how to
apply it to professional problems and problems in everyday life.
|
Sotiris Nikoletseas
University of Patras & Computer Technology Institute (Patras, Greece)
| TITLE: |
|
Algorithms for Wireless Sensor Networks: Design, Analysis and Experimental Evaluation |
| ABSTRACT: |
|
The efficient and robust realization of wireless sensor networks is a
challenging technological and algorithmic task, because of the unique
characteristics and severe limitations of these devices. This talk
presents representative algorithms for important problems in wireless
sensor networks, such as data propagation and energy balance. The
protocol design uses key algorithmic techniques like randomization and
local optimization. Crucial performance properties of the protocols
(correctness, fault-tolerance, scalability) and their trade-offs are
investigated through both analytic means and large scale simulation.
The experimental evaluation of algorithms for such networks is very
beneficial, not only towards validating and fine-tuning algorithmic
design and analysis, but also because of the ability to study the
accurate impact of several important network parameters and
technological details.
|
PROGRAM's DETAILS
Tuesday May 23, 2006
18:00-20:00 Registration
Wednesday May 24, 2006
08:00-09:30 Registration
09:00-10:30 Session 1 (Chair: Maria Serna)
| 09:00-10:00 |
Invited talk: Algorithms for Wireless Sensor Networks:
Design, Analysis and Experimental Evaluation
by Sotiris Nikoletseas
|
| 10:00-10:30 |
Numerical Estimation of the Impact of Interferences on the
Localization Problem in Sensor Networks
by Matthieu Bouget, Pierre Leone, and Jose Rolim
|
10:30-11:15 Coffee break
11:15-12:45 Session 2 (Chair: Sotiris Nikoletseas)
| 11:15-11:45 |
An Efficient Heuristic for the Ring Star Problem
by Thayse Christine S. Dias, Gilberto F. de Sousa Filho,
Elder M. Macambira, Lucidio dos Anjos F. Cabral, and Marcia
Helena C. Fampa
|
| 11:45-12:15 |
An Incremental Model for Combinatorial Maximization Problems
by Jeff Hartline and Alexa Sharp
|
| 12:15-12:45 |
Workload Balancing in Multi-Stage Production Processes
by Siamak Tazari, Matthias Müller-Hannemann, and Karsten Weihe
|
13:00-14:30 Lunch
15:00-16:00 Session 3 (Chair: Christian Blum)
| 15:00-15:30 |
Fault Cryptanalysis and the Shrinking Generator
by Marcin Gomulkiewicz, Miroslaw Kutylowski,
and Pawel Wlaz
|
| 15:30-16:00 |
Some advances in the theory of voting systems based on
experimental algorithms
by Josep Freixas and Xavier Molinero
|
16:00-16:45 Coffee break
16:45-17:45 Session 4 (Chair: Myroslav Kutylowsky)
| 16:45-17:15 |
Practical Construction of k-Nearest Neighbor Graphs in Metric
Spaces
by Rodrigo Paredes, Edgar Chávez, Karina Figueroa, and Gonzalo
Navarro
|
| 17:15-17:45 |
Fast and Simple Approximation of the Diameter and Radius of a
Graph
by Krists Boitmanis, Karlis Freivalds, Peteris Ledins, and Rudolfs Opmanis
|
Thursday, May 25, 2006
09:00-10:30 Session 5 (Chair: Peter Sanders)
| 09:00-9:30 |
Lists on Lists: A Framework for Self-Organizing Lists in
Environments with Locality of Reference
by Abdelrahman Amer and B. John Oommen
|
| 09:30-10:00 |
Lists Revisited: Cache Conscious STL Lists
by Leonor Frias, Jordi Petit, and Salvador Roura
|
| 10:00-10:30 |
Engineering the LOUDS succinct tree representation
by O'Neil Delpratt, Naila Rahman, and Rajeev Raman
|
10:30-11:15 Coffee break
11:15-12:45 Session 6 (Chair: Jon Bentley)
| 11:15-11:45 |
Faster Adaptive Set Intersections for Text Searching
by Jérémy Barbay, Alejandro López-Ortiz and Tyler Lu
|
| 11:45-12:15 |
Compressed Dictionaries: Space Measures, Data Sets, and Experiments
by Ankur Gupta, Wing-Kai Hon, Rahul Shah, and Jeffrey Scott Vitter
|
| 12:15-12:45 |
Efficient Bit-parallel Algorithms for ( , )-matching
by Kimmo Fredriksson and Szymon Grabowski
|
13:00-14:00 Lunch
14:30-19:00 Excursion
Friday, May 26, 2006
09:00-10:30 Session 7 (Chair: Jose Rolim)
| 09:00-10:00 |
Invited talk: Little Experiments for Algorithms
and Life
by Jon Bentley
|
| 10:00-10:30 |
Evaluation of Online Strategies for Reordering Buffers
by Matthias Englert, Heiko Röglin, and Matthias Westermann
|
10:30-11:15 Coffee break
11:15-12:45 Session 8 (Chair: Matthias Müller-Hannemann)
| 11:15-11:45 |
Scheduling Unrelated Parallel Machines Computational Results
by Burkhard Monien and Andreas Woclaw
|
| 11:45-12:15 |
Implementation of Approximation Algorithms for the Max-Min Resource
Sharing Problem
by Mihhail Aizatulin, Florian Diedrich, and Klaus Jansen
|
| 12:15-12:45 |
Column Generation Based Heuristic for a Helicopter Routing Problem
by Lorenza Moreno, Marcus Poggi de Aragăo, and Eduardo Uchoa
|
13:00-14:30 Lunch
15:00-16:00 Session 9 (Chair: Catherine McGeoch)
| 15:00-15:30 |
Kernels for the Vertex Cover Problem on the Preferred Attachment Model
by Josep Díaz, Jordi Petit, and Dimitrios M. Thilikos
|
| 15:30-16:00 |
Practical Partitioning-Based Methods for the Steiner Problem
by Tobias Polzin and Siavash Vahdati Daneshmand
|
16:00-16:45 Coffee break
16:45-17:45 Session 10 (Chair: Jordi Petit)
| 16:45-17:15 |
Algorithmic and Complexity Results for Decompositions of Biological
Networks into Monotone Subsystems
by Bhaskar DasGupta, German A. Enciso, Eduardo Sontag, and Yi Zhang
|
| 17:15-17:45 |
A maximum profit coverage algorithm with application to small
molecules cluster identification}
by Refael Hassin and Einat Or
|
Around 21:00 Conference Dinner (The bus will pick us up at
19:15)
Saturday, May 27, 2006
09:00-10:30 Session 11 (Chair: Josep Diaz)
| 09:00-10:00 |
Invited talk: Algorithmic Challenges in Web
Search Engines
by Ricardo Baeza-Yates
|
| 10:00-10:30 |
On the Least Cost For Proximity Searching in Metric Spaces
by Karina Figueroa, Edgar Chávez, Gonzalo Navarro, and Rodrigo Paredes
|
10:30-11:15 Coffee break
11:15-12:45 Session 12 (Chair: TBA)
| 11:15-11:45 |
Updating Directed Minimum Cost Spanning Trees
by Gerasimos G. Pollatos, Orestis A. Telelis, and Vassilis Zissimopoulos
|
| 11:45-12:15 |
Experiments on Exact Crossing Minimization using Column Generation
by Markus Chimani, Carsten Gutwenger, and Petra Mutzel
|
| 12:15-12:45 |
Goal Directed Shortest Path Queries Using Precomputed Cluster Distances
by Jens Maue, Peter Sanders, and Domagoj Matijevic
|
13:00-14:30 Lunch
|
 |
