Faster Algorithms for k-SUBSET SUM and Variations

We present new, faster pseudopolynomial time algorithms for the k-SUBSET SUM problem, defined as follows: given a set Z of n positive integers and k targets t(1), ... , t(k), determine whether there exist k disjoint subsets Z(1), ... , Z(k) subset of Z, such that Sigma(Z(i)) = t(i), for i = 1, ... , k. Assuming t = max{t(1), ... , t(k)} is the maximum among the given targets, a standard dynamic programming approach based on Bellman's algorithm [3] can solve the problem in O(nt(k)) time. We build upon recent advances on SUBSET SUM due to Koiliaris and Xu [1 6] and Bringmann [1] in order to provide faster algorithms for k-SUBSET SUM. We devise two algorithms: a deterministic one of time complexity (O) over tilde (n(k)/((k+1))t(k)) and a randomised one of (O) over tilde (n + t(k)) complexity. We further demonstrate how these algorithms can be used in order to cope with variations of k-SUBSET SUM, namely SUBSET SUM RATIO, k-SUBSET SUM RATIO and MULTIPLE SUBSET SUM.