29.04.2025: We released a new technical report on "Near-Optimal Minimum Cuts in Hypergraphs at Scale". This is the work of Adil Chhabra, Christian Schulz, Bora Uçar, and Loris Wilwert. In this report, we introduce HeiCut, a scalable algorithm that aggressively reduces hypergraph size via provably exact reductions and optional label propagation contractions before solving a relaxed BIP. Our experiments on over 500 real-world hypergraphs show HeiCut finds the exact minimum cut in 85% of cases and outperforms existing methods by a large margin, sometimes achieving speedups of up to five orders of magnitude. You can find the preprint here.
24.04.2025: We released a new technical report on "From Theory to Practice: Engineering Approximation Algorithms for Dynamic Orientation". This is the work of Ernestine Großmann, Ivor van der Hoog, Henrik Reinstädtler, Eva Rotenberg, Christian Schulz, and Juliette Vlieghe. In this report, we bridge the gap between theory and practice by engineering and evaluating approximation algorithms for dynamically maintaining graph orientations. The implementation allows for a flexible trade-off between efficiency and quality, and achieves significant speedups over prior methods. You can find the preprint here.
02.04.2025: We released a new technical report on "Shared-Memory Hierarchical Process Mapping". This is the work of Christian Schulz and Henning Woydt. In this report, we present the first shared-memory algorithm that uses hierarchical multisection to efficiently map communication-intensive tasks to processing elements, minimizing communication cost while maintaining load balance. You can find the preprint here.
01.04.2025: Three papers of our group have been accepted at the SIAM Conference on Applied and Computational Discrete Algorithms (ACDA25). The first one, Accelerating Reductions Using Graph Neural Networks for the Maximum Weight Independent Set Problem by Ernestine Großmann, Kenneth Langedal, and Christian Schulz. The second paper, Partitioning Trillion Edge Graphs on Edge Devices by Adil Chhabra, Florian Kurpitz, Christian Schulz, and Daniel Seemaier and the third paper, Shared-Memory Hierarchical Process Mapping by Christian Schulz and Henning Woydt.
01.04.2025: Two papers of our group have been accepted at Symposium on Experimental Algorithms (SEA). The first one, Concurrent Iterated Local Search for the Maximum Weight Independent Set Problem by Ernestine Großmann, Kenneth Langedal, and Christian Schulz. The second paper, CluStRE: Streaming Graph Clustering with Multi-Stage Refinement by Adil Chhabra, Shai Dorian Peretz, and Christian Schulz.
20.02.2025: We released a new technical report on "Semi-Streaming Algorithms for Hypergraph Matching". This is the work of Henrik Reinstädtler, S M Ferdous, Alex Pothen, Bora Uçar, and Christian Schulz. In this report, we propose two one-pass streaming algorithms for the NP-hard hypergraph matching problem, achieving strong approximation guarantees with significantly reduced memory consumption. You can find the preprint here.
18.02.2025: We released a new technical report on "Finding Maximum Weight 2-Packing Sets on Arbitrary Graphs". This is the work of Jannick Borowitz, Ernestine Großmann, and Christian Schulz. In this report, we develop novel data reduction rules and new algorithmic approaches for solving the NP-hard Maximum Weight 2-Packing Set problem efficiently. Our preprocessing routine leads to major speedups while improving solution quality and memory usage. You can find the preprint here.
12.02.2025: We released a new technical report on "CluStRE: Streaming Graph Clustering with Multi-Stage Refinement." This is the work of Adil Chhabra, Shai Dorian Peretz, and Christian Schulz. In this report, we introduce a novel streaming graph clustering algorithm that processes large graphs in a streaming setting. You can find the preprint here.
23.12.2024: Our extended paper "FREIGHT: Fast Streaming Hypergraph Partitioning" has been accepted at the Algorithmica journal. Joint work of Kamal Eyubov, Marcelo Fonseca Faraj and Christian Schulz. You can find the paper here
14.12.2024: We released a new technical report on "Accelerating Reductions Using Graph Neural Networks and a New Concurrent Local Search for the Maximum Weight Independent Set Problem." This is the work of Ernestine Großmann, Kenneth Langedal, and Christian Schulz. In this report, we introduce new data reduction rules, utilize a machine learning screening algorithm powered by a Graph Neural Network, and propose a new concurrent metaheuristic called Concurrent Hybrid Iterated Local Search (CHILS). CHILS achieves state-of-the-art performance on benchmark instances. You can find the preprint here.
12.12.2024: We released a new survey on "A Comprehensive Survey of Data Reduction Rules for the Maximum Weighted Independent Set Problem". This is the work of Ernestine Grossmann, Kenneth Langedal and Christian Schulz. You can find the preprint here.
11.10.2024: We released a new technical report on "Partitioning Trillion Edge Graphs on Edge Devices". This is the work of Adil Chhabra, Florian Kurpicz, Christian Schulz, Dominik Schweisgut, Daniel Seemaer. You can find the preprint here.
25.9.2024: We are proud to announce that our team member, Adil Chhabra, has been awarded the prestigious FTI Prize for his outstanding master’s thesis! In his work, Adil explores buffered streaming algorithms for solving the edge partitioning problem.
31.08.2024: Three papers of our group have been accepted at the Algorithm Engineering and Experiments (ALENEX) 2025 conference. The first one, Optimal Neighborhood Exploration for Dynamic Independent Sets by Jannick Borowitz, Ernestine Großmann, and Christian Schulz. The second paper, Engineering Fully Dynamic Exact Δ-Orientation Algorithms by Ernestine Großmann, Henrik Reinstädtler, Christian Schulz, and Fabian Walliser. The third paper, Scalable Multilevel and Memetic Signed Graph Clustering by Marcelo Fonseca Faraj, Felix Hausberger, and Christian Schulz.
14.8.2024: We released a new technical report on "Engineering Algorithms for Hypergraph b-Matching". This is the work of Ernestine Großmann, Felix Joos, Henrik Reinstädtler, and Christian Schulz. You can find the preprint here.
28.7.2024: The student Team HeiCross secured the 6th place in the student ranking of the PACE Challenge 2024 Heuristic Track (link to results). The team is composed out of Shai Dorian Peretz, Alvaro Garmendia Navarro, Tomer Haham, Antonie Wagner and Marlon Dittes and have been supervised by Adil Chhabra, Ernestine Grossmann, Henrik Reinstädtler, Henning Woydt.
26.7.2024: Our DFG project proposal "Engineering Advanced (Hyper)graph b-matching Algorithms" has been accepted.
17.7.2024: We released a new technical report on "Engineering Fully Dynamic Exact Δ-Orientation Algorithms". This is the work of Ernestine Großmann, Henrik Reinstädtler, Christian Schulz and Fabian Walliser. You can find the preprint here.
10.7.2024: We released a new technical report on "Optimal Neighborhood Exploration for Dynamic Independent Sets". This is the work of Jannick Borowitz, Ernestine Großmann and Christian Schulz. You can find the preprint here.
9.7.2024: We added a group picture to our team site! Have a look!
23.6.2024: Two papers of our group have been accepted at the European Symposium on Algorithms. The first one is "Engineering Edge Orientation Algorithms" together with Henrik Reinstädtler, Christian Schulz and Bora Ucar has been accepted at the European Symposium on Algorithms. You can find a preprint here. The second paper is "SubModST: A Fast Generic Solver for Submodular Maximization with Size Constraints" by Henning Martin Woydt, Christian Komusiewicz, Frank Sommer.
20.6.2024: We are pleased to announce the publication of our new guide "Care for ME/CFS - Praxisleitfaden für die Versorgung von ME/CFS Betroffenen." authored by Astrid Hainzl, Johanna Rohrhofer, Johannes Schweighardt, Joachim Hermisson, Kathryn Hoffmann, Martin Komenda-Lett, Golda Schlaff, Christian Schulz, Michael Stingl, Kevin Thonhofer, and Eva Untersmayr. You can access the guide here.
17.6.2024: Our paper "Finding Near-Optimum Weight Independent Sets at Scale" by Ernestine Großmann, Sebastian Lamm, Christian Schulz and Darren Strash, has been accepted at the Journal of Graph Algorithms and Applications.
21.5.2024: We have new group member, Fabian Walliser who joined as a student research assistent -- Welcome!
23.4.2024: We released a new technical report on computing optimal edge orientations. This is the main work of Henrik in collaboration with Bora Uçar. You can find the preprint here.
23.4.2024: We released an update to our technical report on signed multilevel and memetic graph clustering. Our algorithm is now an order of magnitude faster than before. You can find a preprint here.
16.4.2024: We have new scientific visitor, Kenneth Langedal -- Welcome!
15.4.2024: We have new guest lecturer, Manuel Penschuck, who will read the Algorithms and Data Structures I course -- Welcome!
27.3.2024: Two papers of the group have been accepted at the Symposium on Experimental Algorithms SEA24. The paper "Engineering Weighted Connectivity Augmentation Algorithms" by Marcelo Fonseca Faraj, Ernestine Großmann, Felix Joos, Thomas Möller, Christian Schulz and the paper "Buffered Streaming Edge Partitioning" by Adil Chhabra, Marcelo Fonseca Faraj, Daniel Seemaier, Christian Schulz.
1.3.2024: We have new group member, Henning Woydt -- Welcome!
1.11.2023: We have new group member, Adil Chhabra -- Welcome!
19.10.2023: We released an open problems report on "Open Problems in (Hyper)Graph Decomposition". This has been joint work with organizers and participants of Dagstuhl Seminar 23331. You can find the report here.
18.10.2023: Our DFG project proposal "Engineering Algorithms for Process Mapping at Scale" has been accepted.
28.8.2023: Our group member Marcelo Fonseca Faraj successfully defended his PhD! Congratulations!
18.7.2023: Our group receives the best paper award at the Symposium on Experimental Algorithms (SEA23) for the paper "FREIGHT: Fast Streaming Hypergraph Partitioning". Joint work of Kamal Eyubov, Marcelo Fonseca Faraj and Christian Schulz. You can find a preprint here.
11.7.2023: A team of students in the algorithm engineering group aka Team HeiTwin (Dennis Jakob, Nikita-Nick Funk, Thomas Möller, Ernestine Großmann) has achieved remarkable success in the PACE Challenge! They secured the 5th place in the heuristic track (overall ranking) and an impressive 2nd place in the student ranking of the exact track of the challenge. Congratulations!
23.6.2023: Our paper "Faster Local Motif Clustering via Maximum Flow" has been accepted at the European Symposium on Algorithms (ALGO/ESA). Joint work of Adil Chhabra, Marcelo Fonseca Faraj and Christian Schulz. You can find a preprint here.
1.6.2023: We have new group member, Henrik Reinstädtler -- Welcome!
26.4.2023: Prof. Stefan Neumann from KTH Stockholm gave a talk about his recent result "Dynamic Maintenance of Monotone Dynamic Programs and Applications". You can find the talk slides here. We are now actively searching for a master student to engeineer this type of dynamic dynamic programming algorithms in particular for the knapsack problem.
31.3.2023: Our paper "Finding Near-Optimal Weight Independent Sets at Scale" has been accepted at the Genetic and Evolutionary Computation Conference (GECCO). Joint work of Ernestine Großmann, Sebastian Lamm, Christian Schulz and Darren Strash. You can find a preprint here.
31.3.2023: Our paper "A Distributed Multilevel Memetic Algorithm for Signed Graph Clustering" has been accepted at the Genetic and Evolutionary Computation Conference (GECCO) as short-paper. Joint work of Felix Hausberger, Marcelo Fonseca Faraj and Christian Schulz. You can find a preprint here.
27.3.2023: Our paper "FREIGHT: Fast Streaming Hypergraph Partitioning" has been accepted at the Symposium on Experimental Algorithms (SEA23). Joint work of Kamal Eyubov, Marcelo Fonseca Faraj and Christian Schulz. You can find a preprint here.
27.3.2023: Our paper "Arc-Flags Meet Trip-Based Public Transit Routing" has been accepted at the Symposium on Experimental Algorithms (SEA23). Joint work of Ernestine Großmann, Jonas Sauer, Christian Schulz, Patrick Steil. You can find a preprint here.
15.3.2023: Our DFG project proposal "Algorithm Engineering for Dynamic and (Re)Streaming Graph Decomposition Algorithms" has been accepted.
8.3.2023: One paper of our group has been accepted at the SIAM Conference on Applied and Computational Discrete Algorithms (ACDA23). The paper is titled "Engineering Fully Dynamic Delta Orientation Algorithms" and is joint work of Jannick Borowitz, Ernestine Großmann, Christian Schulz. You can find a preprint here.
15.2.2023: Our group released a new report on "Arc-Flags Meet Trip-Based Public Transit Routing" joint work of Ernestine Großmann, Jonas Sauer, Christian Schulz, Patrick Steil. You can find it here.
14.2.2023: Our group released a new report on "FREIGHT: Fast Streaming Hypergraph Partitioning" joint work of Kamal Eyubov, Marcelo Fonseca Faraj and Christian Schulz. You can find it here.
2.2.2023: Our group released a new report on "Improved Exact and Heuristic Algorithms for Maximum Weight Clique" joint work of Roman Erhardt, Kathrin Hanauer, Nils Kriege, Christian Schulz, Darren Strash. You can find it here.
19.1.2023: Our group released a new report on "Faster Local Motif Clustering via Maximum Flows" joint work of Adil Chhabra, Marcelo Fonseca Faraj and Christian Schulz. You can find it here.
18.1.2023: Our group released a new report on "Engineering Fully Dynamic Delta Orientation Algorithms" joint work of Jannick Borowitz, Ernestine Großmann, Christian Schulz. You can find it here.
26.10.2022: Our survey "More Recent Advances in Graph Partitioning" joint work of Ümit V. Çatalyürek, Karen D. Devine, Marcelo F. Faraj, Lars Gottesbüren, Tobias Heuer, Henning Meyerhenke, Peter Sanders, Sebastian Schlag, Christian Schulz, Daniel Seemaier and Dorothea Wagner, has been accepted at ACM Surveys. You can find a preprint here.
15.10.2022: One paper of our group titled "Local Motif Clustering Via Hypergraph Partitioning" together with Adil Chhabra, Marcelo Fonseca Faraj and Christian Schulz has been accepted at ALENEX 2023. A preprint can be found here.
28.9.2022: Prof. Dr. Christian Schulz joined the Steering Committee of the European Symposium on Algorithms (ALGO/ESA).
30.8.2022: Prof. Dr. Christian Schulz is now part of the Steering Committee of Parameterized Algorithms and Computational Experiments (PACE).
3.8.2022: Prof. Dr. Christian Schulz joined the Steering Committee of the Symposium on Experimental Algorithms.
2.8.2022: Our survey "Recent Advances in Fully Dynamic Graph Algorithms" has been accepted for publication at the ACM Journal of Experimental Algorithms (JEA). You can find a preprint here.
21.7.2022: Our paper "O'Reach: Even Faster Reachability in Large Graphs" by Kathrin Hanauer, Christian Schulz and Jonathan Trummer has been accepted for publication at at the special issue of the ACM Journal of Experimental Algorithms for SEA 2021. You can find a preprint here.
11.7.2022: Proceedings of the Symposium on Experimental Algorithms SEA 2022 are out. SEA will happen in Heidelberg at the end of July! You can find it here.
5.7.2022: Our paper "Recursive Multi-Section on the Fly: Shared-Memory Streaming Algorithms for Hierarchical Graph Partitioning and Process Mapping" joint work of Marcelo Fonseca Faraj and Christian Schulz, has been accepted at IEEE Cluster. You can find a preprint here.
28.6.2022: Our paper "Buffered Streaming Graph Partitioning" joint work of Marcelo Fonseca Faraj and Christian Schulz, has been accepted at Journal of Experimental Algorithms. You can find a preprint here.
26.5.2022: We released a new survey "More Recent Advances in Graph Partitioning" joint work of Ümit V. Çatalyürek, Karen D. Devine, Marcelo F. Faraj, Lars Gottesbüren, Tobias Heuer, Henning Meyerhenke, Peter Sanders, Sebastian Schlag, Christian Schulz, Daniel Seemaier and Dorothea Wagner. You can find a preprint here.
11.5.2022: We released a new technical report "Local Motif Clustering Via (Hyper)Graph Partitioning. joint work of Adil Chhabra, Marcelo Fonseca Faraj and Christian Schulz. This paper considers the local graph clustering problem with respect to motif conductance. You can find a preprint here.
2.5.2022: Our manuscript entitled "Local Motif Clustering via (Hyper)Graph Partitioning" was accepted as extended abstract at AAAI International Symposium on Combinatorial Search.
25.3.2022: Our manuscript entitled "High-Quality Hypergraph Partitioning" has been accepted for publication at ACM Journal of Experimental Algorithms. You can find a preprint here.
14.3.2022: Our proposal for a Dagstuhl Meeting on "Recent Trends in Graph Partitioning" has been accepted. The meeting will take place in August 2023.
4.3.2022: Our survey "Recent Advances in Fully Dynamic Graph Algorithms" will appear in the proceedings of the 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND).
2.2.2022: We released a new technical report "Recursive Multi-Section on the Fly: Shared-Memory Streaming Algorithms for Hierarchical Graph Partitioning and Process Mapping" joint work of Marcelo Fonseca Faraj and Christian Schulz. This paper considers the hierarchical streaming graph partitioning problem with applications to process mapping. You can find a preprint here.
21.12.2021: Our minisymposium "Partitioning and Process Mapping for Emerging Architectures" has been accepted at SIAM Parallel Processing (SIAM PP). Joint work with Henning Meyerhenke and George Slota. This is a two part minisymposium. You can find the schedule here and here.
06.12.2021: Prof. Dr. Christian Schulz joins the editorial board of ACM Transactions on Parallel Computing (TOPC) as an Associate Editor for the term January 2022 - December 2024.
24.11.2021: The initial version of the website for SEA is online and available here
22.11.2021: Prof. Dr. Christian Schulz will be the PC Chair of the Symposium on Experimental Algorithms 2022 (SEA'22). Moreover, SEA will take place in Heidelberg.
17.11.2021: Our proposal "Machine Learning for Graph and Hypergraph Clustering Problems" which has been jointly submitted with Bora Ucar from Lyon has been accepted by DAAD. This will enable further cooperation between the Algorithm Engineering Group Heidelberg and Bora Ucar's group in Lyon, France.
2.10.2021: One paper of the group "Practical Fully Dynamic Minimum Cut Algorithms" together with M. Henzinger and A. Noe has been accepted at ALENEX 2022. A preprint can be found here.
20.9.2021: We currently have an open PhD or PostDoc position. See here for details!
19.9.2021: Prof. Dr. Christian Schulz has been invited to give a talk at the Google Scalable Algorithms for Semi-supervised and Unsupervised Learning Workshop 2021.
31.8.2021: Our paper "Faster Support Vector Machines" by Sebastian Schlag, Matthias Schmidt and Christian Schulz, has been accepted for publication at the ACM Journal of Experimental Algorithms (ACM JEA).
3.8.2021: Our DFG project proposal "Algorithm Engineering for Scalable Data Reduction" has been accepted.
24.6.2021: The paper "Deep Multilevel Graph Partitioning" by Lars Gottesbüren, Tobias Heuer, Peter Sanders, Christian Schulz and Daniel Seemaier has been accepted for publication at the 29th Annual European Symposium on Algorithms (ESA).
17.6.2021: We released a new technical report "High Quality Hypergraph Partitioning" joint work with Sebastian Schlag, Tobias Heuer, Lars Gottesbüren, Yaroslav Akhremtsev, Christian Schulz and Peter Sanders. This paper considers the balanced hypergraph partitioning problem. In the TR, we describe all details of our open source hypergraph partitioner KaHyPar which is based on the successful multi-level approach. You can find a preprint here.
9.6.2021: Prof. Dr. Christian Schulz will be PC Chair for the PACE'22 implementation challenge. Ernestine Grossmann, Tobias Heuer and Darren Strash are joining the program committee.
6.5.2021: We released a new technical report on "Deep Multilevel Graph Partitioning" by Lars Gottesbüren, Tobias Heuer, Peter Sanders, Christian Schulz, Daniel Seemaier. You can find a preprint here.
6.5.2021: Two papers of the group have been accepted at the SIAM Conference on Applied and Computational Discrete Algorithms (ACDA21). The paper "Fully-dynamic Weighted Matching Approximation in Practice" by Eugenio Angriman, Henning Meyerhenke, Christian Schulz, Bora Ucar and the paper "Faster Parallel Multiterminal Cuts" by Monika Henzinger, Alexander Noe, Christian Schulz.
29.4.2021: The paper "An MPI-Parallel Algorithm for Mapping Complex Networks onto Hierarchical Architectures" by Maria Predarim, Charilaos Tzovas, Christian Schulz, Henning Meyerhenke has been accepted for publication at the 27th International European Conference on Parallel Computing (Euro-Par).
28.4.2021: We released a new technical report on "Fully-dynamic Weighted Matching Approximation in Practice" joint work with Eugenio Angriman, Henning Meyerhenke, Christian Schulz and Bora Ucar. You can find a preprint here.
9.3.2021: The paper "O'Reach: Even Faster Reachability in Large Graphs" by Kathrin Hanauer, Christian Schulz and Jonathan Trummer has been accepted for publication at the 19th Symposium on Experimental Algorithms (SEA). You can find a preprint here.
1.3.2021: Our survey "Recent Advances in Scalable Graph Generation" together with Manuel Penschuck, Ulrik Brandes, Michael Hamann, Sebastian Lamm, Ulrich Meyer, Ilya Safro, Peter Sanders and Christian Schulz has been accepted as a book chapter for the Massive Graph Analytics book. You can find a preprint here.
23.2.2021: We released a new survey on fully dynamic graph algorithms. You can find it here.
19.2.2021: We released a new TR on buffered streaming graph partitioning. Faster and better than the previous state-of-the-art! You can find it here.
1.2.2021: We have new group member, Ernestine Grossmann -- Welcome!
23.12.2020: We released a survey on recent advances in practical data reduction. It is available here.
16.11.2020: We released mt-KaHIP -- shared-memory parallel high quality graph partitioning. It can be found here.
10.11.2020: One paper of the group "The Future is Big Graphs! A Community View on Graph Processing Systems" together with Sakr et. al has been accepted at Communications of ACM (CACM). A preprint can be found here.
5.10.2020: Four papers of the group have been accepted at SIAM Symposium on Algorithm Engineering and Experiments (ALENEX21).
