2014-05-31

# Faster space-efficient 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 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.

Additional Metadata | |
---|---|

Keywords | Exact exponential time algorithms, Exponential time algorithms, Fine-grained complexity, K-sum, Space-efficient algorithms, Space-time trade-off, Subset sum |

Persistent URL | dx.doi.org/10.1137/17M1158203 |

Journal | SIAM Journal on Computing |

Citation |
Bansal, N, Garg, S, Nederlof, J, & Vyas, N. (2014). Faster space-efficient algorithms for Subset Sum, k -Sum, and related problems. In
SIAM Journal on Computing (Vol. 47, pp. 1755–1777). doi:10.1137/17M1158203 |