Dynamic Subset Sum with Truly Sublinear Processing Time
share
Subset sum is a very old and fundamental problem in theoretical computer science. In this problem, n items with weights w_1, w_2, w_3, …, w_n are given as input and the goal is to find out if there is a subset of them whose weights sum up to a given value t. While the problem is NP-hard in general, when the values are non-negative integer, subset sum can be solved in pseudo-polynomial time O(n+t). In this work, we consider the dynamic variant of subset sum. In this setting, an upper bound is provided in advance to the algorithm and in each operation, either a new item is added to the problem or for a given integer value t ≤, the algorithm is required to output whether there is a subset of items whose sum of weights is equal to t. Unfortunately, none of the existing subset sum algorithms is able to process these operations in truly sublinear time[Truly sublinear means n^1-Ω(1).] in terms of . Our main contribution is an algorithm whose amortized processing time[Since the runtimes are amortized, we do not use separate terms update time and query time for different operations and use processing time for all types of operations.] for each operation is truly sublinear in when the number of operations is at least ^2/3+Ω(1). We also show that when both element addition and element removal are allowed, there is no algorithm that can process each operation in time ^1-Ω(1) on average unless [The strong exponential time hypothesis states that no algorithm can solve the satisfiability problem in time 2^n(1-Ω(1)).] fails.
READ FULL TEXT