Before revision: 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.
After revision: 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 \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.