κ-Partitioning problems for maximizing the minimum load

The optimization versions of the k-PARTITIONING problems are considered in this paper. For the objective to maximize the minimum load of m subsets, we first show that the FOLDING algorithm has a tight worst case ratio of max{2/k,1/m}. Then, we present an algorithm called HARMONIC1 with a worst case ratio at least max{ 1/k, 1/( Σi=1m 1/i +1)}. It concludes the HARMONIC1 is better than FOLDING for k > 2( Σi=1m 1/i + 1). We further show that HARMONICI is asymptotically optimal ordinal algorithm. We also present an algorithm HARMONIC2 for solving the general κi-PARTITIONING problem.