A parallel local-search algorithm for the k-partitioning problem

Presents a new algorithm for the k-partitioning problem which achieves an improved solution quality compared to known heuristics. We apply the principle of so-called “helpful sets”, which has been shown to be very efficient for graph bisection, to the direct k-partitioning problem. The principle is extended in several ways. We introduce a new abstraction technique which shrinks the graph during runtime in a dynamic way, leading to shorter computation times and improved solution qualities. The use of stochastic methods provides further improvements in terms of solution quality. Additionally, we present a parallel implementation of the new heuristic. The parallel algorithm delivers the same solution quality as the sequential one, while providing reasonable parallel efficiency on moderately sized MIMD systems. All results are verified by experiments for various graphs and processor numbers