论文标题
子集总和的快速低空算法
Fast Low-Space Algorithms for Subset Sum
论文作者
论文摘要
我们考虑了规范子集总和问题：给定一个正整数$ a_1，\ ldots，a_n $和一个目标整数$ t $，所有$ i $的$ t> a_i $，确定是否存在$ s \ subseteq [n]众所周知的伪繁殖时间动态编程算法[Bellman，1957年]以$ O（nt）$时间求解子集总和，同时需要$ω（t）$ space。 在本文中，我们使用$ \ tilde o（nt）$运行时间介绍了子集总和算法，并且比贝尔曼（Bellman）的算法以及先前工作的算法要低得多。我们表明，可以用$ \ tilde o（nt）$时间和$ o（\ log（nt））$ space访问$ o（\ log n \ log \ log \ log n+log \ log t）$随机位。这在$ \ tilde o（n t^{1+ \ varepsilon}）$ - 时间，$ \ tilde o（n \ log t）$ - Bringmann的空间算法（SODA 2017）上大大改善。我们还给出了$ \ tilde o（n^{1+\ varepsilon} t）$ - 时间，$ o（\ log（nt））$ - 空间随机算法，对以前的$（nt）^{o（nt）$ - time $ o（\ log log（\ log（nt）$ - 太空algorithms和jak come andube andue andu andu andu andu andu andue and tantane＆tantane tantan tantan tantan^$（nt）^{o（nt）^{o（nt）^{o（nt）^{o（nt）^{o（nt）。凯恩（2010）。此外，我们还提供了$ \ mathrm {poly} \ log（nt）$ - space，$ \ tilde o（n^2 t）$ - 时间确定性算法。 我们还研究子集总和的时空权衡。对于参数$ 1 \ le k \ le \ min \ {n，t \} $，我们提出了一种在$ \ tilde o中运行的随机算法（（（n+t）\ cdot k）$ time和$ o（（t/k）\ mathrm {polylog}（ntt）（nt））$ space。 作为结果的应用，我们给出了$ \ tilde {o}（\ min \ {n^2/\ varepsilon，n/\ varepsilon^2 \}）$ - 时间和$ \ mathrm {polylog}（nt）（nt）$ space algorithm for“ for”
We consider the canonical Subset Sum problem: given a list of positive integers $a_1,\ldots,a_n$ and a target integer $t$ with $t > a_i$ for all $i$, determine if there is an $S \subseteq [n]$ such that $\sum_{i \in S} a_i = t$. The well-known pseudopolynomial-time dynamic programming algorithm [Bellman, 1957] solves Subset Sum in $O(nt)$ time, while requiring $Ω(t)$ space. In this paper we present algorithms for Subset Sum with $\tilde O(nt)$ running time and much lower space requirements than Bellman's algorithm, as well as that of prior work. We show that Subset Sum can be solved in $\tilde O(nt)$ time and $O(\log(nt))$ space with access to $O(\log n \log \log n+\log t)$ random bits. This significantly improves upon the $\tilde O(n t^{1+\varepsilon})$-time, $\tilde O(n\log t)$-space algorithm of Bringmann (SODA 2017). We also give an $\tilde O(n^{1+\varepsilon}t)$-time, $O(\log(nt))$-space randomized algorithm, improving upon previous $(nt)^{O(1)}$-time $O(\log(nt))$-space algorithms by Elberfeld, Jakoby, and Tantau (FOCS 2010), and Kane (2010). In addition, we also give a $\mathrm{poly} \log(nt)$-space, $\tilde O(n^2 t)$-time deterministic algorithm. We also study time-space trade-offs for Subset Sum. For parameter $1\le k\le \min\{n,t\}$, we present a randomized algorithm running in $\tilde O((n+t)\cdot k)$ time and $O((t/k) \mathrm{polylog} (nt))$ space. As an application of our results, we give an $\tilde{O}(\min\{n^2/\varepsilon, n/\varepsilon^2\})$-time and $\mathrm{polylog}(nt)$-space algorithm for "weak" $\varepsilon$-approximations of Subset Sum.
