Fast exact and approximate algorithms for k-partition and scheduling independent tasks

AbstractWe consider the problem of partitioning a multiset of integers into k disjoint subsets whose sums are closest to a given set of target numbers. (This can also be viewed as a problem of scheduling independent tasks on uniform machines.) We present a new algorithm which works for problems with a large number of different summands (m̄) whose values are bounded by l = O(m̄32/k2logm̄). While a generalization of the dynamic programming approach yields an O(lk−1mk) algorithm, our algorithm is substantially faster - approaching linear (O(kl log l)) in some cases. A modification of the algorithm gives an approximate solution with a relative error o(1/k2l) in O(kllogl) time