WEA 2006

EXPERIMENTAL ALGORITHMS

Fifth International Workshop

May 24-27, 2006

Menorca Island, Spain
 

 
Bookmark us
Contact us
CfP flyer

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