The k-partitioning problem is defined as follows: Given a set of items {I_1,I_2,...,I_n} where item I_j is of weight w_j ≥ 0, find a partition S_1,S_2,...,S_m of this set with |S_i| = k such that the maximum weight of all subsets S_i 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.
展开▼
