Name
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2016 | 10.1137/17M1158203 | SIAM JOURNAL ON COMPUTING |
Keywords | Field | DocType |
space-efficient algorithms,k-sum,subset sum,exact exponential time algorithms,fine-grained complexity,space-time trade-off,exponential time algorithms | Integer,Discrete mathematics,Binary logarithm,Randomized algorithm,Combinatorics,Subset sum problem,Polynomial,Algorithm,Knapsack problem,Mathematics,Random access,Bounded function | Journal |
Volume | Issue | ISSN |
47 | 5 | 0097-5397 |
Citations | PageRank | References |
0 | 0.34 | 0 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Nikhil Bansal | 1 | 3043 | 230.41 |
| Shashwat Garg | 2 | 17 | 4.87 |
| Jesper Nederlof | 3 | 294 | 24.22 |
| Nikhil Vyas | 4 | 1 | 1.71 |