SPP 1307: Algorithm Engineering
Overview
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 365足彩投注_365体育投注@s 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
- Project duration:
- 01/2007 - 12/2016
- Funded by:
- DFG
- Subprojects:
- Websites:
-
Homepage
DFG-Datenbank gepris
More Information
Results
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 (365足彩投注_365体育投注@he 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 (365足彩投注_365体育投注@he 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 (365足彩投注_365体育投注@he 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 (365足彩投注_365体育投注@he 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 (365足彩投注_365体育投注@he 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 (365足彩投注_365体育投注@he 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 (365足彩投注_365体育投注@he 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 (365足彩投注_365体育投注@he 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 (365足彩投注_365体育投注@he 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 (365足彩投注_365体育投注@he 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 (365足彩投注_365体育投注@he 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 (365足彩投注_365体育投注@he 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 (365足彩投注_365体育投注@he 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 (365足彩投注_365体育投注@he 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 (365足彩投注_365体育投注@he 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 (365足彩投注_365体育投注@he 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 (365足彩投注_365体育投注@he 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 (365足彩投注_365体育投注@he 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 (365足彩投注_365体育投注@he online unter https://doi.org/10.1016/j.cor.2014.09.010)Projektbezogene Publikationen (Auswahl)