  Partitioning a graph into blocks of roughly equal weight while cutting only
few edges is a fundamental problem in computer science with numerous practical
applications. While shared-memory parallel partitioners have recently matured
to achieve the same quality as widely used sequential partitioners, there is
still a pronounced quality gap between distributed partitioners and their
sequential counterparts. In this work, we shrink this gap considerably by
describing the engineering of an unconstrained local search algorithm suitable
for distributed partitioners. We integrate the proposed algorithm in a
distributed multilevel partitioner. Our extensive experiments show that the
resulting algorithm scales to thousands of PEs while computing cuts that are,
on average, only 3.5% larger than those of a state-of-the-art high-quality
shared-memory partitioner. Compared to previous distributed partitioners, we
obtain on average 6.8% smaller cuts than the best-performing competitor while
being more than 9 times faster.
