TOP
Suche auf der Schloss Dagstuhl Webseite
Sie suchen nach Informationen auf den Webseiten der einzelnen Seminare? - Dann:
Nicht fündig geworden? - Einige unserer Dienste laufen auf separaten Webseiten mit jeweils eigener Suche. Bitte beachten Sie folgende Liste:
Schloss Dagstuhl - LZI - Logo
Schloss Dagstuhl Services
Seminare
Innerhalb dieser Seite:
Externe Seiten:
  • DOOR (zum Registrieren eines Dagstuhl Aufenthaltes)
  • DOSA (zum Beantragen künftiger Dagstuhl Seminare oder Dagstuhl Perspektiven Workshops)
Publishing
Innerhalb dieser Seite:
Externe Seiten:
dblp
Innerhalb dieser Seite:
Externe Seiten:
  • die Informatik-Bibliographiedatenbank dblp


Dagstuhl-Seminar 13391

Algorithm Engineering

( 22. Sep – 27. Sep, 2013 )

(zum Vergrößern in der Bildmitte klicken)

Permalink
Bitte benutzen Sie folgende Kurz-Url zum Verlinken dieser Seite: https://www.dagstuhl.de/13391

Organisatoren

Kontakt


Programm

Motivation

The algorithm engineering approach consists of a cycle of algorithm design, analysis, implementation, and experimental evaluation, with the aim of bridging the gap between theory and practice in the area of algorithms. This cycle of phases is driven by falsifiable hypotheses validated by experiments. Moreover, real-world instances often have direct impact on this cycle since they often expose modelling and analysis shortcomings. In the last fifteen years, this approach to algorithmic research has gained increasing attention. Prominent success stories in algorithm engineering include the algorithms library LEDA, the linear program solver CPLEX, the traveling salesman suite CONCORDE, speed-up techniques for shortest paths computation, as well as graph partitioning and the computation of Steiner trees. All these topics are driven by the need for efficient algorithms and libraries for problems that appear frequently in real-world applications. The seminar will cover all methodological aspects of algorithm engineering. Examples are:

The scientific method in algorithmics. One aspect of algorithm engineering is the scientific method, where research on algorithms is interpreted as in other disciplines such as physics and life sciences: the observation of a phenomenon that is not yet understood is investigated via falsifiable hypotheses as explanations of the phenomena, and experimental evaluations to test these hypotheses. That way not only emperical evidence on the behavior of algorithms is attained but also new theoretical insights are sought. Experimental algorithmics is already a core component of algorithm engineering from its very beginning. However, the design of reasonable experiments, the use of meaningful test instances, and reproducibility of experiments are still issues to be discussed in order to derive a common understanding and agree on a best practice.

The use of modern computer architecture. Exploiting the full potential of a modern computer poses many interesting new challenges for algorithm engineering: ever increasing parallelism, deep memory hierarchies, and heterogeneous architectures. Algorithms should be tailored to utilize multiple cores, but also access memory efficiently, taking into account issues such as data locality. Nowadays the use of GPUs, which are increasingly common in modern servers, is an important issue for efficient algorithm implementation. This is in particular interesting for frequently used and "classical" algorithms.

Certifying algorithms. An effective way to ensure correct results of algorithm implementations are certifying algorithms. The idea is to check each returned result for correctness using a simple checker. It then suffices to test or perhaps verify the checker. Making checking fast implies interesting algorithmic questions when checking is aided by certificates of correctness computed by the main algorithm.

Experiences from previous Dagstuhl Seminars show that the interaction between different scientific communities stimulates methodological discussions. This exchange is in particular important for neighboring scientific communities who typically meet at separate conferences. For this seminar, we plan to focus on web search, large graphs and social networks in order to also address the scientific WWW and Social Media community. In these fields, methods from algorithm engineering are applied. However, these scientists typically don’t publish at algorithm engineering conferences.

The aim of this seminar is to bring together researchers with different backgrounds in order to strengthen and foster collaborations and to identify key research directions for the future. In particular, the seminar is intended to foster the exchange between algorithm engineering and scientists from the web search community. While the dominant goal of the seminar is the exchange of current research developments and discussion of topical subjects, we also intend to bring algorithm engineering forward as a still evolving and expanding field in computer science. Therefore we will plan dedicated discussion sessions on methodological questions, but will also address research related issues like future DIMACS Implementation Challenges.


Summary

Topics of the Seminar

The seminar covered all methodological aspects of algorithm engineering. Examples are the scientific method in algorithmics, the use of modern computer architecture in algorithmics, and certifying algorithms. These aspects were also addressed in dedicated discussion sessions.

Science of Algorithms

One aspect of algorithm engineering is the scientific method, where research on algorithms is interpreted as in other disciplines such as physics and life sciences: the observation of a phenomenon that is not yet understood is investigated via falsifiable hypotheses as explanations of the phenomena, and experimental evaluations to test these hypotheses. That way not only empirical evidence on the behavior of algorithms is attained but also new theoretical insights are sought. Experimental algorithmics is already a core component of algorithm engineering from its very beginning. However, the design of reasonable experiments, the use of meaningful test instances, and reproducibility of experiments are still issues to be discussed in order to derive a common understanding and agree on a best practice.

Manycore and GPU Algorithms

Exploiting the full potential of a modern computer poses many interesting new challenges for algorithm engineering: ever increasing parallelism, deep memory hierarchies, and heterogeneous architectures. Algorithms should be tailored to utilize multiple cores, but also access memory efficiently, taking into account issues such as data locality. Nowadays the use of GPUs, which are increasingly common in modern servers, is an important issue for efficient algorithm implementation. This is in particular interesting for frequently used and "classical" algorithms.

Certifying Algorithms

An effective way to ensure correct results of algorithm implementations are certifying algorithms. The idea is to check each returned result for correctness using a simple checker. It then suffices to test or perhaps verify the checker. Making checking fast implies interesting algorithmic questions when checking is aided by certificates of correctness computed by the main algorithm.

Focus Topic: Web Search and Large Graphs

Experiences from previous Dagstuhl seminars showed that the interaction between different scientific communities stimulates methodological discussions. This exchange is in particular important for neighboring scientific communities who typically meet at separate conferences. For this seminar, we focus on web search, large graphs and social networks in order to also address the scientific WWW and Social Media community. In these fields, methods from algorithm engineering are applied. However, these scientists typically don't publish at the algorithm engineering conferences mentioned above but meet and publish at conferences like the "International World Wide Web Conference", the "ACM Conference on Hypertext and Hypermedia" or the "International AAAI Conference on Weblogs and Social Media".

Search engines work with a large amount of data, making high-performance algorithms and data structures very important. Relevant problems include fast indexing, text and query processing, and relevance computation. The latter involves a large web graph. Web-enabled applications give raise to other large graphs, such as social networks, like "friend graphs" or e-mail graphs induced by message origin-destination pairs. Algorithms on such graphs are of great interest. For example, identifying interest-based sub-communities (e.g., classical music fans) enables better service experience or contextual advertisement.

Aims

The aim of this seminar was to bring together researchers with different backgrounds, e.g., from algorithm and datastructures, computational geometry, combinatorial optimization, parallel algorithms and algorithm engineering in order to strengthen and foster collaborations and to identify key research directions for the future. In particular, the seminar was intended to foster the exchange between algorithm engineering and scientists from the web search community. While the dominant goal of the seminar was the exchange of current research developments and discussion of topical subjects, it also contributed to bring algorithm engineering forward as a still evolving and expanding field in computer science. The seminar program included four dedicated discussion sessions on methodological questions, as well as research related issues like future DIMACS Implementation Challenges.

Conclusion

The organizers decided to schedule talks and discussions not grouped according to topics but provide a vivid mix of different research questions and results. According to the composition of the seminar participants, not all topics were covered equally well. For example, certifying algorithms were not addressed in detail. On Monday, Renato Werneck gave a short report on the "11th DIMACS Implementation Challenge on Steiner Tree Problems" taking place in 2013/14. The program of Monday afternoon was concluded by a panel discussion on "Empirical and Theoretical Approaches to Algorithm Design: Synergies and Opportunities". The second panel discussion on "Benchmarks and reproducibility of experiments" took place on Tuesday. The third panel discussion on Thursday focused on "Promoting and advancing the field" and on Friday a discussion about "Teaching Algorithm Engineering" concluded the program.

The seminar hosted 39 participants. Besides presentations and panel discussions the program offered room for bilateral discussions and working groups. Schloss Dagstuhl and its staff provided a very convenient and stimulating environment. The seminar participants appreciated the cordial atmosphere which improved mutual understanding and inspiration. The organizers of this seminar wish to thank all those who helped make the workshop a fruitful research experience.

Copyright Andrew V. Goldberg, Giuseppe F. Italiano, David S. Johnson, and Dorothea Wagner

Teilnehmer
  • Hannah Bast (Universität Freiburg, DE) [dblp]
  • Jon Louis Bentley (Avaya - Basking Ridge, US) [dblp]
  • Robert E. Bixby (Rice University - Houston, US) [dblp]
  • Gerth Stølting Brodal (Aarhus University, DK) [dblp]
  • Kevin Buchin (TU Eindhoven, NL) [dblp]
  • Markus Chimani (Universität Osnabrück, DE) [dblp]
  • Frank Dehne (Carleton University - Ottawa, CA) [dblp]
  • Daniel Delling (Microsoft Corp. - Mountain View, US) [dblp]
  • Julian Dibbelt (KIT - Karlsruher Institut für Technologie, DE) [dblp]
  • Rudolf Fleischer (German University of Technology - Oman, OM) [dblp]
  • Andrew V. Goldberg (Microsoft Corp. - Mountain View, US) [dblp]
  • Holger H. Hoos (University of British Columbia - Vancouver, CA) [dblp]
  • Falk Hüffner (TU Berlin, DE) [dblp]
  • Giuseppe F. Italiano (University of Rome "Tor Vergata", IT) [dblp]
  • David S. Johnson (New York, US) [dblp]
  • Andrea Kappes (KIT - Karlsruher Institut für Technologie, DE) [dblp]
  • Jyrki Katajainen (University of Copenhagen, DK) [dblp]
  • Jürgen Lerner (Universität Konstanz, DE) [dblp]
  • Kurt Mehlhorn (MPI für Informatik - Saarbrücken, DE) [dblp]
  • Ulrich Carsten Meyer (Goethe-Universität - Frankfurt a. M., DE) [dblp]
  • Friedhelm Meyer auf der Heide (Universität Paderborn, DE) [dblp]
  • Henning Meyerhenke (KIT - Karlsruher Institut für Technologie, DE) [dblp]
  • Shin-ichi Minato (Hokkaido University, JP) [dblp]
  • Rolf H. Möhring (TU Berlin, DE) [dblp]
  • Matthias Müller-Hannemann (Martin-Luther-Universität Halle-Wittenberg, DE) [dblp]
  • Petra Mutzel (TU Dortmund, DE) [dblp]
  • Patrick K. Nicholson (MPI für Informatik - Saarbrücken, DE) [dblp]
  • Yoshio Okamoto (The University of Electro-Communications - Tokyo, JP) [dblp]
  • Marina Papatriantafilou (Chalmers UT - Göteborg, SE) [dblp]
  • Alejandro Salinger (Universität des Saarlandes, DE) [dblp]
  • Peter Sanders (KIT - Karlsruher Institut für Technologie, DE) [dblp]
  • Federico Santaroni (University of Rome "Tor Vergata", IT) [dblp]
  • Sabine Storandt (Universität Freiburg, DE) [dblp]
  • Dorothea Wagner (KIT - Karlsruher Institut für Technologie, DE) [dblp]
  • Roger Wattenhofer (ETH Zürich, CH) [dblp]
  • Renato Werneck (Microsoft Corp. - Mountain View, US) [dblp]
  • Christos Zaroliagis (CTI & University of Patras, GR) [dblp]
  • Liang Zhao (KIT - Karlsruher Institut für Technologie, DE) [dblp]
  • Katharina A. Zweig (TU Kaiserslautern, DE) [dblp]

Verwandte Seminare
  • Dagstuhl-Seminar 10261: Algorithm Engineering (2010-06-27 - 2010-07-02) (Details)

Klassifikation
  • data bases / information retrieval
  • data structures / algorithms / complexity
  • world wide web / internet

Schlagworte
  • experimental algorithmics
  • parallel and distributed computing
  • web search
  • social networks