5 papers
High-Quality Multi-Constraint Hypergraph Partitioning via Greedy Rebalancing
Nikolai Maas
Multi-constraint hypergraph partitioning is a generalization of balanced partitioning, where the vertex set of a hypergraph is partitioned such that the inter-block connectivity of…
Deterministic Parallel High-Quality Hypergraph Partitioning
Robert Krause, Lars Gottesbüren, Nikolai Maas
We present a deterministic parallel multilevel algorithm for balanced hypergraph partitioning that matches the state of the art for non-deterministic algorithms. Deterministic para…
Parallel Unconstrained Local Search for Partitioning Irregular Graphs
Nikolai Maas, Lars Gottesbüren, Daniel Seemaier
We present new refinement heuristics for the balanced graph partitioning problem that break with an age-old rule. Traditionally, local search only permits moves that keep the block…
Linear-Time Multilevel Graph Partitioning via Edge Sparsification
Lars Gottesbüren, Nikolai Maas, Dominik Rosch +2
The current landscape of balanced graph partitioning is divided into high-quality but expensive multilevel algorithms and cheaper approaches with linear running time, such as singl…
Engineering Optimal Parallel Task Scheduling
Matthew Akram, Nikolai Maas, Peter Sanders +1
The NP-hard scheduling problem P||C_max encompasses a set of tasks with known execution time which must be mapped to a set of identical machines such that the overall completion ti…