Algorithm Engineering

Abstract

The workshop Algorithm Engineering, organized by Giuseppe Italiano (Roma), Petra Mutzel (Dortmund), Peter Sanders (Karlsruhe), and Martin Skutella (Dortmund) was held May 6th – May 12th, 2007. The goal of the workshop was to bring together researchers with different background, e.g., from combinatorial optimization, algorithmic theory, and algorithm engineering, in order to strengthen and foster collaborations in the area of algorithm engineering and to identify key research directions for the future. There were 47 international participants out of which 23 mainly work in the area of algorithm engineering, 11 in algorithm theory, and 13 in combinatorial optimization. A considerable number of participants visited the Oberwolfach Institute (MFO) for the first time.

In five survey talks given by renowned specialists in the field, the state of the art in selected areas of high interest was demonstrated. The introductory talk was presented by Giuseppe Italiano (Roma) who gave “a personal and historical perspective” of algorithm engineering. Bill Cook (Atlanta) presented the newest results as well as engineering efforts for solving huge TSP instances. Friedhelm Meyer auf der Heide (Paderborn) suggested new algorithmic challenges in the area of Computer Graphics. Ian Munro (Waterloo) introduced the audience into the area of succinct data structures which is getting increasingly important with huge data sets. In this context, also external memory and cache-oblivious algorithms are getting growing interest. The survey talk by Gerth Brodal (Aarhus) presented theory and practice for these type of algorithms.

In addition, we organized a series of sessions containing shorter contributions of roughly 30 minutes. Here, we particularly encouraged young researchers to present their recent results. The focus of the program lay on recent developments in various areas that are relevant for the broad topic of algorithm engineering. Examples are mathematical programming, external memory algorithms, succinct data structures, resilient data structures, dynamic data structures, online algorithms, graph algorithms, geometric computation, analysis of local search algorithms, and algorithmic game-theory. In total, we had 32 talks of which 15 can be assigned to the area of algorithm engineering, 8 to the area of algorithmic theory, and 7 to the area of combinatorial optimization, which we think was an ideal mixture for the purpose of this workshop. We found it encouraging that after the talks a lot of discussion took place between the participants.

We also like to mention that Peter Sanders (Karlsruhe) introduced the new DFG Priority Program 1307 Algorithm Engineering, which will start in fall 2007. As the coordinator of this program he pointed out the specific goals of the program and the chances for the area of algorithm engineering. All of the participants had the chance to discuss different aspects of algorithm engineering in the open problem session on Thursday evening.

In our view, and as expressed by many of the participants, the workshop was a great success. We (including many participants) have learned a lot during this week, also from the three different research communities present at the workshop, and got many new ideas for exciting research projects. The program of the workshop was well-received by the participants as the good quality of presentations and the enthusiasm of the speakers and the audience gave raise to joint research among the participants. In particular exchange between young researchers and experienced scientists was promoted.

We wish to thank Oberwolfach for this unique opportunity to bring together the three different research groups at this great place in order to strengthen the area of algorithm engineering.

The following collection of abstracts in chronological order gives a more detailed overview of the program.