论文标题
弦乐测量的空间有效确定性近似
Space Efficient Deterministic Approximation of String Measures
论文作者
论文摘要
我们研究了以下三个字符串测量的近似算法，这些算法在实践中广泛使用：编辑距离（ED），最长的常见子序列（LCS）和最长增加的序列（LIS）。所有三个问题都可以通过在多项式时间内使用的标准算法完全解决，其中大约$θ（n）$空间，其中$ n $是输入长度，我们的目标是设计确定性近似算法，这些算法在多项式时间内运行，空间较小。 为此，我们设计了几种算法，这些算法对于所有三个问题都达到了$ 1+ε$或$1-ε$的近似，其中$ε> 0 $可以是任何常数，甚至略微降低的常数。我们的算法是灵活的，可以调整以实现以下两个参数范围：1）对于任何常数$δ> 0 $，space $ n^δ$，运行时间基本上与标准算法基本相同或略大;和2）空格$ \ mathsf {polylog}（n）$带有（较大的）多项式运行时间，这在史蒂夫的类（\ textbf {sc}）中放置了三个问题的近似版本。我们的算法在空间复杂性方面显着改善了先前的结果，在该算法中，所有已知结果都需要使用至少$ω（\ sqrt {n}）$。我们的某些算法也可以适用于在非对称流模型[SS13]中起作用，并输出相应的序列。此外，我们的结果可用于改善Farhadi ET的最新结果。 al。 [FHRS20]大约在非对称流模型中近似ED，从[FHRS20]中的指数缩短到多项式。 我们的算法基于使用递归如Savitch定理[SAV70]的想法，以及对以前的技术进行仔细改编以使递归起作用。一路上，我们还从最长的共同子角度减少了新的日志空间，从最长的序列增加了，这可能是独立的。
We study approximation algorithms for the following three string measures that are widely used in practice: edit distance (ED), longest common subsequence (LCS), and longest increasing sequence (LIS). All three problems can be solved exactly by standard algorithms that run in polynomial time with roughly $Θ(n)$ space, where $n$ is the input length, and our goal is to design deterministic approximation algorithms that run in polynomial time with significantly smaller space. Towards this, we design several algorithms that achieve $1+ε$ or $1-ε$ approximation for all three problems, where $ε>0$ can be any constant and even slightly sub constant. Our algorithms are flexible and can be adjusted to achieve the following two regimes of parameters: 1) space $n^δ$ for any constant $δ>0$ with running time essentially the same as or slightly more than the standard algorithms; and 2) space $\mathsf{polylog}(n)$ with (a larger) polynomial running time, which puts the approximation versions of the three problems in Steve's class (\textbf{SC}). Our algorithms significantly improve previous results in terms of space complexity, where all known results need to use space at least $Ω(\sqrt{n})$. Some of our algorithms can also be adapted to work in the asymmetric streaming model [SS13], and output the corresponding sequence. Furthermore, our results can be used to improve a recent result by Farhadi et. al. [FHRS20] about approximating ED in the asymmetric streaming model, reducing the running time from being exponential in [FHRS20] to a polynomial. Our algorithms are based on the idea of using recursion as in Savitch's theorem [Sav70], and a careful adaption of previous techniques to make the recursion work. Along the way we also give a new logspace reduction from longest common subsequence to longest increasing sequence, which may be of independent interest.
