We study approximation algorithms for the following three string measures that are widely used in practice: edit distance  , longest common subsequence  , and longest increasing sequence .\ All three problems can be solved exactly by standard algorithms that run in polynomial time with roughly O (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+\epsilon or 1-\epsilon approximation for all three problems, where \epsilon>0 can be any constant  . Our algorithms use space n^{\delta for any constant \delta>0 and have running time essentially the same as or slightly more than the standard algorithms   . Our algorithms significantly improve previous results in terms of space complexity, where all known results need to use space at least \Omega(n). Some of our algorithms can also be adapted to work in the asymmetric streaming model \mbox{%DIFAUXCMD saks2013space\hspace{0pt}%DIFAUXCMD }  , and output the corresponding sequence.  ]  ]  Our algorithms are based on the idea of using recursion as in Savitch's theorem \mbox{%DIFAUXCMD \cite{Savitch70}\hspace{0pt}%DIFAUXCMD }  , and a careful modification 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.
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 \Theta (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+\epsilon or 1-\epsilon approximation for all three problems, where \epsilon>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^\delta for any constant \delta>0 with running time essentially the same as or slightly more than the standard algorithms ; and 2) space \mathsf{polylog SC) . Our algorithms significantly improve previous results in terms of space complexity, where all known results need to use space at least \Omega(n). Some of our algorithms can also be adapted to work in the asymmetric streaming model \hspace{0pt}%DIFAUXCMD } 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 }\hspace{0pt}%DIFAUXCMD } 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.
A
(ED)
A
(LCS)
R
.\
(LIS).
R
O
\Theta
A
and even slightly sub constant
R
use space n^{\delta
are flexible and can be adjusted to achieve the following two regimes of parameters: 1) space n^\delta
R
and have
with
A
; and 2) space \mathsf{polylog
A
SC
A
)
D
\mbox{%DIFAUXCMD saks2013space
A
SS13
A
Furthermore, our results can be used to improve a recent result by Farhadi et. al.
A
FHRS20
A
about approximating ED in the asymmetric streaming model, reducing the running time from being exponential in
A
FHRS20
A
to a polynomial.
D
\mbox{%DIFAUXCMD \cite{Savitch70
A
Sav70
R
modification
adaption