Name
Abstract | ||
|---|---|---|
We study the exact time complexity of the Subset Sum problem. Our focus is on instances that lack additive structure in the sense that the sums one can form from the subsets of the given integers are not strongly concentrated on any particular integer value. We present a randomized algorithm that runs in O(2(0.3399n) B-4) time on instances with the property that no value can arise as a sum of more than B different subsets of the n given integers. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.4230/LIPIcs.STACS.2015.48 | Leibniz International Proceedings in Informatics |
Keywords | Field | DocType |
subset sum,additive combinatorics,exponential-time algorithm,homomorphic hashing,Littlewood-Offord problem | Integer,Discrete mathematics,Combinatorics,Littlewood–Offord problem,Subset sum problem,Time complexity,Mathematics | Conference |
Volume | ISSN | Citations |
30 | 1868-8969 | 2 |
PageRank | References | Authors |
0.38 | 10 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| per austrin | 1 | 187 | 18.31 |
| Petteri Kaski | 2 | 912 | 66.03 |
| Mikko Koivisto | 3 | 803 | 55.81 |
| Jesper Nederlof | 4 | 294 | 24.22 |