SPP 1307: Algorithm Engineering
Überblick
Effiziente Algorithmen und Datenstrukturen sind Grundvoraussetzung für anspruchsvolle Computeranwendungen, die mit großen Datenmengen auf immer komplexerer Hardware umgehen. Zum Beispiel haben Algorithmen für Internetsuchmaschinen die Art verändert, wie wir mit Wissen und Information umgehen. Ausgefeilte Algorithmen zur Sequenzierung des menschlichen Genoms haben diesen entscheidenden Durchbruch der Biowissenschaft um mehrere Jahre beschleunigt. Algorithmik - die systematische Entwicklung effizienter Algorithmen - ist deshalb entscheidend für die Umsetzung technologischer Möglichkeiten in Anwendungen mit großer Bedeutung für Technik, Wirtschaft, Wissenschaft und unser tägliches Leben.
Die Lösung der anstehenden Probleme wird aber behindert durch eine über Jahrzehnte gewachsene Kluft zwischen dem Wissensstand der Algorithmentheorie und der praktischen Anwendung von Algorithmen. Das Algorithm Engineering tritt an, diese Kluft zwischen Theorie und Praxis zu überbrücken. Schlüssel dazu ist eine breitere Methodik, die den traditionellen Dreiklang der Algorithmentheorie von Entwurf, Analyse und beweisbaren Leistungsgarantien deutlich erweitert. Kern des Algorithm Engineering ist ein Kreislauf aus Entwurf, Analyse, Implementierung und experimenteller Bewertung von Algorithmen. Hinzu kommen vielfältige Querbezüge zu konkreten Anwendungen, Arbeit an wieder verwendbaren Bibliotheken von Algorithmenimplementierungen und realistische Modelle für moderne Hardware und wichtige algorithmische Fragestellungen.
Das Schwerpunktprogramm soll zu einem nachhaltigen Innovationsschub bei der Anwendung von Algorithmen führen, indem es das Algorithm Engineering schneller vorantreibt, weiter entwickelt, breiter etabliert und stärker vernetzt. Wir sehen eine echte Chance, dass das Algorithm Engineering zu einem weltweit sichtbaren Markenzeichen der deutschen Informatik wird, das auch die Wettbewerbsfähigkeit der deutschen Wirtschaft stärkt. Langfristiges Ziel ist eine nachhaltige Überbrückung von Lücken zwischen Theorie und Praxis.
DFG-Verfahren Schwerpunktprogramme
Internationaler Bezug Schweiz
Projekte
Algorithm Engineering für dynamische Graphenoptimierungsprobleme in konkreten Anwendungen (Antragsteller Müller-Hannemann, Matthias)
Algorithm Engineering für MONET und verwandte Abdeckungsprobleme (Antragsteller Mundhenk, Martin)
Algorithm Engineering für Netzwerkprobleme (Antragstellerin Albers, Susanne)
Algorithm Engineering für Probleme der Computergrafik (Antragsteller Meyer auf der Heide, Friedhelm)
Algorithm Engineering für Real-Time Scheduling und Routing (Antragsteller Eisenbrand, Friedrich; Skutella, Martin)
Algorithm Engineering zur Methodenentwicklung im randomisierten Runden (Antragsteller Doerr, Benjamin)
Algorithmen für komplexe Schedulingprobleme (Antragsteller Möhring, Rolf H.)
Algorithms for Data Stream Processing (Antragsteller Kliemann, Lasse)
Algorithms for Modern Hardware: Flash Memory (Antragsteller Meyer, Ulrich)
Anwendungsorientierte Indexstrukturen für Approximate Pattern Matching (Antragsteller Mayr, Ernst W.)
Clusterung statischer und zeitbehafteter Graphen (Antragstellerin Wagner, Dorothea)
Design, Analyse, Implementierung und experimentelle Auswertung von Algorithmen zum Genomvergleich mit der SeqAn Softwarebibliothek (Antragsteller Reinert, Knut)
Effiziente Indexdatenstrukturen und Sprachverarbeitung für semantische Volltextsuche (Antragstellerin Bast, Hannah)
Effiziente Suche in sehr großen Textmengen, Datenbanken und Ontologien (Antragstellerin Bast, Hannah)
Einfache und schnelle Implementierung von exakten Optimierungsalgorithmen mit SCIL (Antragsteller Althaus, Ernst; Buchheim, Christoph)
Engineering efficient algorithms for the basic algorithmic toolbox with emphasis on algorithm libraries, memory hierarchies and parallelism (Antragsteller Sanders, Peter)
Engineering von Matching- und Überdeckungsalgorithmen in großen Graphen und Hypergraphen (Antragsteller Srivastav, Anand)
Entwicklung einer praxisnahen Theorie für Clusteringalgorithmen durch datengetriebene Modellierung und Analyse (Antragsteller Blömer, Johannes; Sohler, Christian)
Entwurf und Analyse anwendungsbezogener geometrischer Algorithmen (Antragsteller Alt, Helmut)
Exakte Ganzzahlige Optimierung (Antragsteller Grötschel, Martin)
Externe zielgerichtete Suche in impliziten Graphen (Antragsteller Steffen, Bernhard)
Generische Dekompositionsalgorithmen für ganzzahlige Programme (Antragsteller Lübbecke, Marco)
Gestörte Diffusion für die Partitionierung und Clusteranalyse von Graphen (Antragsteller Monien, Burkhard)
Koordination und Infrastruktur, Präsentation der Ergebnisse des SPP auf internationalen Workshops und Tagungen (Antragsteller Sanders, Peter)
Kunst! - Exakte Algorithmen für Kunstgalerieprobleme (Antragsteller Kröller, Alexander)
Planarisierungsverfahren im Automatischen Zeichnen von Graphen (Antragstellerin Mutzel, Petra)
RoboRithmics: Algorithmische und praktische Methoden zur Steuerung eines autonomen Explorationsroboters (Antragsteller Fekete, Sándor)
Robuste Algorithmen für diskrete Optimierungsprobleme (Antragstellerin Schöbel, Anita)
Schnellere Algorithmen für harte Probleme wie Subset Sum, Syndromdekodierung in linearen Codes und dem Kürzesten Vektor Problem mit zahlreichen Anwendungen in der Komplexitätstheorie und der Kryptographie (Antragsteller May, Alexander)
Stochastische Lokale Suche bei SAT-Solvern (Antragsteller Schöning, Uwe)
Strukturbasiertes Algorithm Engineering für SAT-Solving (Antragsteller Kaufmann, Ph.D., Michael)
Sprecher Professor Dr. Peter Sanders
Key Facts
- Laufzeit:
- 01/2007 - 12/2016
- Gefördert durch:
- DFG
- Unterprojekte:
- Websites:
-
Homepage
DFG-Datenbank gepris
Detailinformationen
Ergebnisse
A new diffusion-based multilevel algorithm for computing graph partitions of very high quality. Proceedings of the 2008 IEEE International Symposium on Parallel and Distributed Processing (IPDPS). IEEE Computer Society, 2008. Henning Meyerhenke, Burkhard Monien, Thomas Sauerwald (Siehe online unter https://dx.doi.org/10.1109/IPDPS.2008.4536237) Interactive exploration of chemical space with scaffold hunter. Nature Chemical Biology, Vol. 5. 2009, pp. 581–583. Stefan Wetzel, Karsten Klein, Steffen Renner, Daniel Rauh, Tudor I. Oprea, Petra Mutzel, Herbert Waldmann (Siehe online unter https://doi.org/10.1038/nchembio.187) An experimental study of new and known online packet buffering algorithms. Algorithmica, Vol. 57. 2010, Issue 4, pp. 725–746. Susanne Albers, Tobias Jacobs (Siehe online unter https://doi.org/10.1007/s00453-008-9230-y) Clustering for metric and nonmetric distance measures. ACM Transactions on Algorithms, Vol. 6. 2010, No. 4, 59. Marcel R. Ackermann, Johannes Blömer, Christian Sohler (Siehe online unter https://doi.org/10.1145/1824777.1824779) Submodular Formulations for Range Assignment Problems. International Symposium on Combinatorial Optimization (ISCO). Electronic Notes in Discrete Mathematics, Vol. 36. 2010, pp. 239-246. Frank Baumann, Christoph Buchheim (Siehe online unter https://doi.org/10.1016/j.endm.2010.05.031) Beyond unit propagation in SAT solving. In: P. M. Pardalos, S. Rebennack (Eds.), Experimental Algorithms: 10th International Symposium, SEA 2011, Kolimpari, Chania, Crete, Greece, May 5-7, 2011. Proceedings, (Lecture Notes in Computer Science, vol. 6630), Springer, 2011, pp. 267–279. Michael Kaufmann, Stephan Kottler (Siehe online unter https://doi.org/10.1007/978-3-642-20662-7_23) Energy-efficient sorting using solid state disks. Sustainable Computing: Sustainable Computing: Informatics and Systems, Vol. 1. 2011, Issue 2: Special Issue on Selected Papers from the 2010 Green Computing Conference, pp. 151-163. Andreas Beckmann, Ulrich Meyer, Peter Sanders, Johannes Singler (Siehe online unter https://doi.org/10.1016/j.suscom.2011.02.004) How to apply sat-solving for the equivalence test of monotone normal forms. In: Theory and Applications of Satisfiability Testing - SAT 2011: 14th International Conference, SAT 2011, Ann Arbor, MI, USA, June 19-22, 2011. Proceedings. (Lecture Notes in Computer Science, 6695), 2011, pp. 105–119. Martin Mundhenk, Robert Zeranski (Siehe online unter https://doi.org/10.1007/978-3-642-21581-0_10) Integrated sequencing and scheduling in coil coating. Management Science, Vol. 57.2011, Issue 4, pp. 647–666. Wiebke Höhn, Felix G. König, Marco E. Lübbecke, Rolf H. Möhring (Siehe online unter https://doi.org/10.1287/mnsc.1100.1302) Broccoli: Semantic full-text search at your fingertips. CoRR, abs/1207.2615, 2012. Hannah Bast, Florian Bäurle, Björn Buchhold, Elmar Haussmann (Siehe online unter https://arxiv.org/pdf/1207.2615.pdf) Certifying feasibility and objective value of linear programs. Operations Research Letters, Vol. 40. 2012, Issue 4, pp. 292-297. Ernst Althaus, Daniel Dumitriu (Siehe online unter https://doi.org/10.1016/j.orl.2012.03.004) Shape matching by random sampling. Theoretical Computer Science, Vol. 442. 2012, pp. 2-12. Helmut Alt, Ludmila Scharf (Siehe online unter https://doi.org/10.1016/j.tcs.2010.03.023) Dynamic Graph Clustering Combining Modularity and Smoothness. ACM Journal of Experimental Algorithmics, Vol. 18. 2013, Issue 1, pp 1.1–1.29. Robert Görke, Pascal Maillard, Andrea Schumm, Christian Staudt, Dorothea Wagner (Siehe online unter https://doi.org/10.1145/2444016.2444021) Spherical visibility sampling. (In 24th Eurographics Symposium on Rendering). Computer Graphics Forum, Vol. 32. 2013, Issue 4, pp. 49-58. Benjamin Eikel, Claudius Jähn, Matthias Fischer, Friedhelm Meyer auf der Heide (Siehe online unter https://doi.org/10.1111/cgf.12150) The Satisfiability Problem: Algorithms and Analyses. (Mathematik für Anwendungen, Band 3), Lehmanns Media, 2013, 184 S., ISBN 978-3-86541-527-1. Jacobo Toran, Uwe Schöning Randomized rounding in the presence of a cardinality constraint. ACM Journal of Experimental Algorithmics, Vol. 19.2014. Benjamin Doerr, Magnus Wahlström (Siehe online unter https://doi.org/10.1145/2594409) The price of strict and light robustness in timetable information. Transportation Science, Vol. 48. 2014, No. 2, pp. 225–242. M. Goerigk, M. Schmidt, A. Schöbel, M. Knoth, M. Müller-Hannemann (Siehe online unter https://doi.org/10.1287/trsc.2013.0470) Automatic Dantzig-Wolfe reformulation of mixed integer programs. Mathematical Programming, Vol. 149. 2015, Issue 1-2, pp. 391–424. M. Bergner, A. Caprara, A. Ceselli, F. Furini, M.E. Lübbecke, E. Malaguti, E. Traversi (Siehe online unter https://doi.org/10.1007/s10107-014-0761-5) Facets for art gallery problems. Algorithmica, Vol. 73. 2015, pp. 411–440. Sándor P. Fekete, Stephan Friedrichs, Alexander Kröller, Christiane Schmidt (Siehe online unter https://doi.org/10.1007/s00453-014-9961-x) The robust knapsack problem with queries. Computers & Operations Research, Vol. 55. 2015, pp. 12-22. M. Goerigk, M. Gupta, J. Ide, A. Schöbel, S. Sen (Siehe online unter https://doi.org/10.1016/j.cor.2014.09.010)Projektbezogene Publikationen (Auswahl)