Finite alphabet ,
finite set R of strings from .
such that w is a subsequence of each ,
i.e. one can get w by taking away letters from each x.
Length of the subsequence, i.e., .
Approximable within ,
where m is the length of the
shortest string in R .
Not approximable within
where n is the maximum of
,  and .
Transformation from MAXIMUM INDEPENDENT SET.
APX-complete if the size of the alphabet
is fixed 
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