Algorithm engineering (AE) consists of the design, the theoretical analysis, the implementation, and the experimental evaluation of algorithms, with the aim of bridging the gap between theory and practice in the area of algorithms. In the last decade, this approach to algorithmic research has gained increasing attention.
The aim of this seminar was to bring together researchers with different backgrounds, 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.
The seminar was attended by 29 participants from both academia and industry. Much was accomplished, fostered by the productive atmosphere of the Dagstuhl Center. Here we describe some of the more important achievements.
The program consisted of a wide variety of presentations and discussion sessions. The presentations included several survey lectures, in addition to more specialized talks. David Bader and Roman Dementiev presented surveys of the challenges of multi-core and many-core architectures for algorithm engineers, and convinced us that the new computer architectures will strongly influence future algorithmic research. Rüdiger Schultz surveyed the area of stochastic programming, including bi-level problems (e.g., Stackelberg games) and risk aversion. A key issue is that, for at least some of the input data, only the probabilistic distribution is known in advance. This area was initially studied by mathematicians and experts in mathematical programming, but has been recently discovered by computer scientists. Catherine McGeoch and David Johnson provided surveys on experimental procedures. Giuseppe Italiano gave an overview of resilient algorithms and data structures, and Philippas Tsigas discussed lock-free data structures, both areas of increasing algorithmic interest. Peter Sanders described the aim of the German priority program SPP 1307 Algorithm Engineering which began running in 2007.
Beyond the survey lectures, highlights of the seminar included lectures on routing in networks (e.g., transit networks for public transportation, and highway networks), on specific stochastic optimization and game-theoretic problems (e.g., 2-stage stochastic Steiner tree, stochastic ad allocation, pricing lotteries, and risk-averse models), on mixed integer linear programming approaches (e.g., MIP domination), and on clustering algorithms.
Arguably the most-appreciated features of the Seminar were the four lively open discussion sessions, which led to several concrete proposals for the future of the field which, as a result of the workshop, are now being actively pursued.
It is our impression that the participants enjoyed the great scientific atmosphere offered by Schloss Dagstuhl, and profited from the scientific program and the fruitful discussions. We are grateful for having had the opportunity to organize this seminar. Special thanks are due to Carsten Gutwenger for his assistance in the organization and the running of the seminar.
- David A. Bader (Georgia Institute of Technology - Atlanta, US) [dblp]
- Hannah Bast (Universität Freiburg, DE) [dblp]
- Robert E. Bixby (Rice University - Houston, US) [dblp]
- Patrick Briest (Universität Paderborn, DE) [dblp]
- Roman Dementiev (Intel GmbH - Feldkirchen, DE) [dblp]
- Arno Eigenwillig (Google Switzerland, CH)
- Andrew V. Goldberg (Microsoft Corp. - Mountain View, US) [dblp]
- Zonghao Gu (Gurobi Optimization - Houston, US) [dblp]
- Carsten Gutwenger (TU Dortmund, DE) [dblp]
- Giuseppe F. Italiano (University of Rome "Tor Vergata", IT) [dblp]
- David S. Johnson (AT&T Labs Research - Florham Park, US) [dblp]
- Michael Jünger (Universität Köln, DE) [dblp]
- Luigi Laura (Sapienza University of Rome, IT) [dblp]
- Ivana Ljubic (Universität Wien, AT)
- Catherine C. McGeoch (Amherst College, US) [dblp]
- Henning Meyerhenke (Georgia Institute of Technology - Atlanta, US) [dblp]
- Petra Mutzel (TU Dortmund, DE) [dblp]
- Gonzalo Navarro (University of Chile - Santiago de Chile, CL) [dblp]
- Marina Papatriantafilou (Chalmers UT - Göteborg, SE) [dblp]
- Kirk Pruhs (University of Pittsburgh, US) [dblp]
- Peter Sanders (KIT - Karlsruher Institut für Technologie, DE) [dblp]
- Federico Santaroni (University of Rome "Tor Vergata", IT) [dblp]
- Rüdiger Schultz (Universität Duisburg-Essen, DE)
- Clifford Stein (Columbia University, US) [dblp]
- Chaitanya Swamy (University of Waterloo, CA)
- Philippas Tsigas (Chalmers UT - Göteborg, SE) [dblp]
- Jose Verschae (TU Berlin, DE) [dblp]
- Dorothea Wagner (KIT - Karlsruher Institut für Technologie, DE) [dblp]
- Gerhard J. Woeginger (TU Eindhoven, NL) [dblp]
- Dagstuhl Seminar 13391: Algorithm Engineering (2013-09-22 - 2013-09-27) (Details)
- data bases
- information retrieval
- data structures
- experimental algorithmics
- game theory
- parallel and distributed algorithms