Approximation Algorithms for LCS and LIS with Truly Improved Running Times
share
Longest common subsequence (𝖫𝖢𝖲) is a classic and central problem in combinatorial optimization. While 𝖫𝖢𝖲 admits a quadratic time solution, recent evidence suggests that solving the problem may be impossible in truly subquadratic time. A special case of 𝖫𝖢𝖲 wherein each character appears at most once in every string is equivalent to the longest increasing subsequence problem (𝖫𝖨𝖲) which can be solved in quasilinear time. In this work, we present novel algorithms for approximating 𝖫𝖢𝖲 in truly subquadratic time and 𝖫𝖨𝖲 in truly sublinear time. Our approximation factors depend on the ratio of the optimal solution size over the input size. We denote this ratio by λ and obtain the following results for 𝖫𝖢𝖲 and 𝖫𝖨𝖲 without any prior knowledge of λ. ∙ A truly subquadratic time algorithm for 𝖫𝖢𝖲 with approximation factor Ω(λ^3). ∙A truly sublinear time algorithm for 𝖫𝖨𝖲 with approximation factor Ω(λ^3). Triangle inequality was recently used by [Boroujeni, Ehsani, Ghodsi, HajiAghayi and Seddighin SODA 2018] and [Charkraborty, Das, Goldenberg, Koucky and Saks FOCS 2018] to present new approximation algorithms for edit distance. Our techniques for 𝖫𝖢𝖲 extend the notion of triangle inequality to non-metric settings.
READ FULL TEXT