Denna tjänst avvecklas 2026-01-19. Läs mer här (länk)

Denna tjänst avvecklas 2026-01-19. Läs mer här (länk)

LONGEST COMMON SUBSEQUENCE

• INSTANCE: Finite alphabet $\Sigma$, finite set R of strings from $\Sigma^*$.

• SOLUTION: A string $w\in\Sigma^*$ such that w is a subsequence of each $x\in R$, i.e. one can get w by taking away letters from each x.

• MEASURE: Length of the subsequence, i.e., $\vert w\vert$.

  
  

• Good News: Approximable within $O(m/\log m)$, where m is the length of the shortest string in R [223].

• Bad News: Not approximable within $n^{1/4-\varepsilon }$ for any $\varepsilon >0$, where n is the maximum of $\vert R\vert$ and $\vert\Sigma\vert$ [77], [275] and [68].

• Comment: Transformation from MAXIMUM INDEPENDENT SET. APX-complete if the size of the alphabet $\Sigma$ is fixed [275] and [89]. Variation in which the objective is to find the shortest maximal common subsequence (a subsequence that cannot be extended to a longer common subsequence) is not approximable within $\vert R\vert^{1-\varepsilon }$ for any $\varepsilon >0$ [170].

• Garey and Johnson: SR10