The k-partitioning problem is defined as follows: Given a set of items {I1, I2, …, In} where item Ij is of weight wj ≥ 0, find a partition S1, S2, … Sm of this set with |Si| = k such that the maximum weight of all subsets Si is minimal. k-partitioning is strongly related to the classical multiprocessor scheduling problem of minimizing the makespan on identical machines. This paper provides suitable tools for the construction of algorithms which solve exactly the problem. Several approximation algorithms are presented for this NP-hard problem. The worst-case behavior of the algorithms is analyzed. The best of these algorithms achieves a performance bound of 4/3.
