论文标题
带有真正均方根处理时间的动态子集总和
Dynamic Subset Sum with Truly Sublinear Processing Time
论文作者
论文摘要
子集总和是理论计算机科学中的一个非常古老且基本的问题。在此问题中，给出$ n $项目$ w_1，w_2，w_3，\ ldots，w_n $作为输入给出，目标是找出是否有其权重总计为给定值$ t $的子集。虽然问题通常是NP - hard，但是当值是非负整数时，可以在伪级别的时间$〜\ widetilde o（n+t）$中求解子集总和。 在这项工作中，我们考虑子集总和的动态变体。在这种情况下，提前提供了上限$ \ tmax $，并且在每个操作中，要么将新项目添加到问题中，要么是给定的整数值$ t \ leq \ tmax $，是否需要算法才能输出是否存在其权重等于$ t $的项目。不幸的是，现有的子集总和算法都无法在真正的sublrinear Time \ footNote {真正的sublrinear表示$ n^{1-ω（1）} $。}中处理这些操作。 我们的主要贡献是一种算法，其摊销处理时间\ footNote {由于运行时间是摊销的，我们不使用单独的术语更新时间和查询时间来进行不同操作。 We also show that when both element addition and element removal are allowed, there is no algorithm that can process each operation in time $\tmax^{1-Ω(1)}$ on average unless \textsf{SETH}\footnote{The \textit{strong exponential time hypothesis} states that no algorithm can solve the satisfiability problem in time $ 2^{n（1-Ω（1））} $。}失败。
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, \ldots, 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 $~\widetilde O(n+t)$. In this work, we consider the dynamic variant of subset sum. In this setting, an upper bound $\tmax$ 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 \leq \tmax$, 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\footnote{Truly sublinear means $n^{1-Ω(1)}$.} in terms of $\tmax$. Our main contribution is an algorithm whose amortized processing time\footnote{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 $\tmax$ when the number of operations is at least $\tmax^{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 $\tmax^{1-Ω(1)}$ on average unless \textsf{SETH}\footnote{The \textit{strong exponential time hypothesis} states that no algorithm can solve the satisfiability problem in time $2^{n(1-Ω(1))}$.} fails.
