FASTER SPACE-EFFICIENT ALGORITHMS FOR SUBSET SUM, k-SUM, AND RELATED PROBLEMS

摘要

We present randomized algorithms that solve subset sum and knapsack instances with n items in O*((20.86n)) time, where the O* (.) notation suppresses factors polynomial in the input size, and polynomial space, assuming random read-only access to exponentially many random bits. These results can be extended to solve binary integer programming on n variables with few constraints in a similar running time. We also show that for any constant k = 2, random instances of k-sum can be solved using O(n(k-0.5) polylog(n)) time and O(log n) space, without the assumption of random access to random bits. Underlying these results is an algorithm that determines whether two given lists of length n with integers bounded by a polynomial in n share a common value. Assuming random read-only access to random bits, we show that this problem can be solved using O(log n) space significantly faster than the trivial O(n(2)) time algorithm if no value occurs too often in the same list.