A multicore-based algorithm for optimal multi-way number partitioning

Abstract

The Multi-Way Number Partitioning (MWNP) problem is to divide a multiset of n numbers into k subsets in such a way that the largest subset sum is minimized. MWNP is an NP-hard combinatorial optimization problem which requires a high computational time. It has applications in many areas, such as processor scheduling and public key encryption. In this paper, we design a fast parallel algorithm that finds an exact solution for the MWNP problem based on the recursive principle of optimality. The practical studies on a multicore system and data set generated in the range \([1,2^{48}-1]\) show that the proposed parallel algorithm is able to reduce the running time of the corresponding sequential algorithm. The results of the parallel algorithm show that, using 16 cores, the algorithm achieves, on average, a speedup of 10 and a percentage \(90\%\) of improvement in running time over its sequential counterpart.