20140531
Faster spaceefficient algorithms for Subset Sum, k Sum, and related problems
Publication
Publication
SIAM Journal on Computing , Volume 47  Issue 5 p. 1755 1777
We present randomized algorithms that solve subset sum and knapsack instances with n items in O^{∗} (2^{0.86n}) time, where the O^{∗} (∙ ) notation suppresses factors polynomial in the input size, and polynomial space, assuming random readonly 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 kSum 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 readonly 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.
Additional Metadata  

, , , , , ,  
doi.org/10.1137/17M1158203  
SIAM Journal on Computing  
Organisation  Centrum Wiskunde & Informatica, Amsterdam, The Netherlands 
Bansal, N, Garg, S, Nederlof, J, & Vyas, N. (2014). Faster spaceefficient algorithms for Subset Sum, k Sum, and related problems. In SIAM Journal on Computing (Vol. 47, pp. 1755–1777). doi:10.1137/17M1158203
