SPP 1307:  Algorithm Engineering

• Subject Area: Computer Science, Systems and Electrical Engineering
• Term: from 2007 to 2016
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 29058954

Efficient algorithms and data structures are prerequisites for high-level computer applications dealing with large amounts of data on increasingly complex hardware. One example: Algorithms for internet search engines have changed the way we deal with knowledge and information. Sophisticated algorithms for the sequencing of the human genome have made this breakthrough in biological sciences possible many years earlier than anticipated. Therefore, algorithmics, i. e. the systematic development of efficient algorithms, is vital to the realisation of technical possibilities in applications of great importance to technology, the economy, science and our everyday life.
But solutions to the problems at hand are impeded by the gulf between algorithm theory's scientific state of research and the practical application of algorithms that has been growing for decades. Algorithm Engineering aims at bridging this gap between theory and practice, the key being a broader methodology, which significantly expands the traditional triad of algorithm theory: conception, analysis and provable performance guaranties. At the core of Algorithm Engineering there is a circle of conception, analysis, implementation and experimental evaluation of algorithms. In addition, there are various cross references to concrete applications, work on reusable algorithm implementation libraries for modern hardware and important algorithmic questions.
The Priority Programme aims at initiating a lasting drive towards innovation in the application of algorithms by promoting Algorithm Engineering, developing it further, establishing it on a broader base and integrating it more effectively. We see a real chance for Algorithm Engineering to become a worldwide visible trademark of German computer sciences strengthening the German economy's ability to compete. The long-term goal is bridging the gaps between theory and practice.

• DFG Programme: Priority Programmes
• International Connection: Switzerland

Projects

• Algorithm Engineering für dynamische Graphenoptimierungsprobleme in konkreten Anwendungen (Applicant Müller-Hannemann, Matthias )
• Algorithm Engineering für MONET und verwandte Abdeckungsprobleme (Applicant Mundhenk, Martin )
• Algorithm Engineering für Netzwerkprobleme (Applicant Albers, Susanne )
• Algorithm Engineering für Probleme der Computergrafik (Applicant Meyer auf der Heide, Friedhelm )
• Algorithm Engineering für Real-Time Scheduling und Routing (Applicants Eisenbrand, Friedrich ;  Skutella, Martin )
• Algorithm Engineering zur Methodenentwicklung im randomisierten Runden (Applicant Doerr, Benjamin )
• Algorithmen für komplexe Schedulingprobleme (Applicant Möhring, Rolf H. )
• Algorithms for Data Stream Processing (Applicant Kliemann, Lasse )
• Algorithms for Modern Hardware: Flash Memory (Applicant Meyer, Ulrich )
• Anwendungsorientierte Indexstrukturen für Approximate Pattern Matching (Applicant Mayr, Ernst W. )
• Clustering of Static and Temporal Graphs (Applicant Wagner, Dorothea )
• Design, analysis, development and experimental validation of genome comparison algorithms using the SeqAn library (Applicant Reinert, Knut )
• Development of a practical theory for clustering algorithms through data-driven modeling and analysis (Applicants Blömer, Johannes ;  Sohler, Christian )
• Efficient index data structures and natural language processing for semantic full-text search (Applicant Bast, Hannah )
• Effiziente Suche in sehr großen Textmengen, Datenbanken und Ontologien (Applicant Bast, Hannah )
• Einfache und schnelle Implementierung von exakten Optimierungsalgorithmen mit SCIL (Applicants Althaus, Ernst ;  Buchheim, Christoph )
• Engineering efficient algorithms for the basic algorithmic toolbox with emphasis on algorithm libraries, memory hierarchies and parallelism (Applicant Sanders, Peter )
• Engineering of Matching and Covering Algorithms in Large Graphs and Hypergraphs (Applicant Srivastav, Anand )
• Entwurf und Analyse anwendungsbezogener geometrischer Algorithmen (Applicant Alt, Helmut )
• Exakte Ganzzahlige Optimierung (Applicant Grötschel, Martin )
• Externe zielgerichtete Suche in impliziten Graphen (Applicant Steffen, Bernhard )
• Faster algorithms for hard problems like subset sum, syndrome decoding in linear codes and the shortest vector problem, with various applications in complexity theory and cryptography (Applicant May, Alexander )
• Generic Decomposition Algorithms for Integer Programs (Applicant Lübbecke, Marco )
• Gestörte Diffusion für die Partitionierung und Clusteranalyse von Graphen (Applicant Monien, Burkhard )
• Koordination und Infrastruktur, Präsentation der Ergebnisse des SPP auf internationalen Workshops und Tagungen (Applicant Sanders, Peter )
• Kunst! - Exact Algorithms for Art Gallery Variants (Applicant Kröller, Alexander )
• Planarisierungsverfahren im Automatischen Zeichnen von Graphen (Applicant Mutzel, Petra )
• RoboRithmics: Algorithmische und praktische Methoden zur Steuerung eines autonomen Explorationsroboters (Applicant Fekete, Sándor )
• Robust optimization algorithms (Applicant Schöbel, Anita )
• Stochastische Lokale Suche bei SAT-Solvern (Applicant Schöning, Uwe )
• Structure-based Algorithm Engineering for SAT-Solving (Applicant Kaufmann, Ph.D., Michael )

• Spokesperson: Professor Dr. Peter Sanders