Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Reducing approximate Longest Common Subsequence to approximate Edit
  Distance   Given a pair of strings, the problems of computing their Longest Common
Subsequence and Edit Distance have been extensively studied for decades. For
exact algorithms, LCS and Edit Distance (with character insertions and
deletions) are equivalent; the state of the art running time is (almost)
quadratic and this is tight under plausible fine-grained complexity
assumptions. But for approximation algorithms the picture is different: there
is a long line of works with improved approximation factors for Edit Distance,
but for LCS (with binary strings) only a trivial $1/2$-approximation was known.
In this work we give a reduction from approximate LCS to approximate Edit
Distance, yielding the first efficient $(1/2+\epsilon)$-approximation algorithm
for LCS for some constant $\epsilon>0$.

15
The categories of this paper are: nucl-ex
35
The categories of this paper are: mtrl-th
21
The categories of this paper are: adap-org
29
The categories of this paper are: funct-an
34
The categories of this paper are: chem-ph
30
The categories of this paper are: q-alg
0
The categories of this paper are: hep-ph
36
The categories of this paper are: cmp-lg
20
The categories of this paper are: acc-phys
14
The categories of this paper are: math-ph
2
The categories of this paper are: math
7
The categories of this paper are: hep-th
12
The categories of this paper are: nucl-th
10
The categories of this paper are: q-bio
32
The categories of this paper are: atom-ph
9
The categories of this paper are: nlin