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

Final Report

Final Report Year 2015

No abstract available

Publications

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
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
An experimental study of new and known online packet buffering algorithms. Algorithmica, Vol. 57. 2010, Issue 4, pp. 725–746.
Susanne Albers, Tobias Jacobs
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
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
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
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
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
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
Broccoli: Semantic full-text search at your fingertips. CoRR, abs/1207.2615, 2012.
Hannah Bast, Florian Bäurle, Björn Buchhold, Elmar Haussmann
Certifying feasibility and objective value of linear programs. Operations Research Letters, Vol. 40. 2012, Issue 4, pp. 292-297.
Ernst Althaus, Daniel Dumitriu
Shape matching by random sampling. Theoretical Computer Science, Vol. 442. 2012, pp. 2-12.
Helmut Alt, Ludmila Scharf
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
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
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
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
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
Facets for art gallery problems. Algorithmica, Vol. 73. 2015, pp. 411–440.
Sándor P. Fekete, Stephan Friedrichs, Alexander Kröller, Christiane Schmidt
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

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