Heidelberg University | Algorithm Engineering Group | Amazon Scholar
My group engineers high-performance C++ solvers for NP-hard combinatorial problems, then ships them as open source. We care about both theoretical quality guarantees and real-world speed.
Our research sits at the intersection of algorithm theory and high-performance engineering. We attack NP-hard problems on graphs and hypergraphs through multilevel methods, evolutionary algorithms, data reduction, kernelization, local search, and parallelism.
All of the below, accessible from Python with a single install:
python -m venv .venv && source .venv/bin/activate
pip install chszlablib
CHSZLabLib wraps 350k+ lines of C++ into a consistent Python API with zero-copy NumPy arrays. 26 algorithm modules, one Graph / HyperGraph interface. Designed to be usable by both humans and AI agents.
Splitting large graphs into balanced pieces while minimizing the edges cut between them. This is the foundation for parallel computing, VLSI design, route planning, and scientific simulations. Unified in the KaHIP org.
| Problem | Solver | What it does |
|---|---|---|
| Graph Partitioning | KaHIP | Multilevel k-way partitioning in Strong/Eco/Fast modes, evolutionary, distributed (ParHIP), edge partitioning, node ordering |
| Hypergraph Partitioning | KaHyPar | n-level hypergraph partitioning with direct k-way and recursive bisection |
| Parallel Hypergraph Part. | Mt-KaHyPar | Multi-threaded hypergraph partitioning for massive instances |
| Parallel Partitioning | KaMinPar | Shared-memory and distributed-memory parallel graph partitioning |
| Streaming Partitioning | HeiStream | Buffered streaming graph partitioning for graphs that don't fit in memory |
| Compressed Streaming | StreamCPI | Memory-efficient streaming partitioning via run-length compression |
| Streaming Hypergraph Part. | FREIGHT | Fast one-pass streaming hypergraph partitioning (SEA 2023 Best Paper) |
Finding minimum cuts, maximum cuts, and natural communities in networks. Unified in the KaHIP org.
| Problem | Solver | What it does |
|---|---|---|
| Minimum Cut | VieCut | Shared-memory parallel exact and inexact minimum cuts, cactus representations, multiterminal cuts |
| Maximum Cut | fpt-max-cut | FPT kernelization + exact/heuristic solvers for max-cut |
| Hypergraph Min-Cut | HeiCut | Exact minimum cuts in hypergraphs using FPT kernelization |
| Connectivity Augmentation | HeiConnect | Weighted connectivity augmentation via greedy heuristics, local search, and ILP-based exact solvers |
| Community Detection | VieClus | Evolutionary modularity-maximizing graph clustering |
| Correlation Clustering | SCC | Multilevel and memetic correlation clustering on signed graphs |
| Motif Clustering | HeidelbergMotifClustering | Triangle-motif-based local clustering via flow/partitioning |
| Streaming Clustering | CluStRE | Streaming graph clustering with multi-stage refinement |
Finding the largest set of non-adjacent vertices, or the heaviest independent set, in a graph. Fundamental NP-hard problems with applications in scheduling, resource allocation, and network analysis. Unified in the KaMIS org.
| Problem | Solver | What it does |
|---|---|---|
| Maximum Independent Set | KaMIS | Branch-and-reduce, evolutionary, local search solvers for large sparse graphs |
| Max Weight Independent Set | CHILS | Concurrent local search heuristic for MWIS |
| GNN-Guided Reductions | LearnAndReduce | Graph neural network guided preprocessing for MWIS |
| Hypergraph Indep. Set | HyperMIS | Kernelization + ILP for hypergraph independent sets |
| Hypergraph b-Matching | HeiHGM/Bmatching | Solver for b-matching in hypergraphs using reductions, ILP, and local search |
| Streaming Hypergraph Matching | HeiHGM/Streaming | Streaming algorithms for hypergraph matching |
| 2-Packing Set | red2pack | Branch-and-reduce solver for the 2-packing set problem |
Maintaining solutions as graphs change over time, without recomputing from scratch. Unified in the DynGraphLab org.
| Problem | Solver | What it does |
|---|---|---|
| Dynamic Edge Orientation | DynDeltaOrientation | Fully dynamic exact and heuristic delta-orientation |
| Dynamic Orient. Approx. | DynDeltaApprox | Dynamic edge orientation approximation algorithms |
| Dynamic Matching | DynMatch | Fully dynamic maximal matching algorithms |
| Dynamic Indep. Set | DynWMIS | Fully dynamic maximum weight independent set |
| Dynamic Reachability | DynReach | Fully dynamic reachability algorithms |
Mapping communication graphs of parallel applications onto processor topologies to minimize communication overhead. Unified in the KaHIP org.
| Problem | Solver | What it does |
|---|---|---|
| Process Mapping | VieM | Multilevel process mapping and sparse quadratic assignment |
| Shared-Memory Mapping | SharedMap | Parallel algorithm for hierarchical process mapping |
| Integrated Mapping | IntegratedProcessMapping | Multi-level integrated process mapping |
| Streaming Mapping | OnlineMultiSection | Streaming process mapping |
| Problem | Solver | What it does |
|---|---|---|
| Edge Orientation | HeiOrient | Heidelberg edge orientation algorithms |
| Graph Generation | KaGen | Karlsruhe graph generation for benchmarking |
| Graph Drawing | KaDraw | Karlsruhe graph drawing |
| Longest Paths | KaLP | Karlsruhe longest paths |
| Support Vector Machines | KaSVM | Multilevel support vector machine |
| Transit Routing | Arc-FlagTB | Public transit routing with arc-flag trip-based algorithms |
- DIMACS Implementation Challenge Winner (Graph Partitioning and Clustering)
- PACE Challenge Winner (Vertex Cover, 2019)
- Best Paper Award, IPDPS 2018 (Communication-free Massively Distributed Graph Generation)
- Best Paper Award, IEEE CLUSTER 2020 (Efficient Process-to-Node Mapping)
- Best Paper Award, SEA 2023 (FREIGHT: Fast Streaming Hypergraph Partitioning)
- Heinz Billing Prize and KIT Doctoral Award
- 120+ publications across ACM, IEEE, SIAM
- Steering Committee Chair, SIAM ALENEX
- Leading the Algorithm Engineering Group at Heidelberg University
- Amazon Scholar working on supply chain optimization
- Shipping open source solvers for NP-hard graph problems at scale
- Bridging theory and practice: quality guarantees that actually run fast
"The goal is not just to prove that a fast algorithm exists, but to build one that people actually use."