, finite set
R
of strings from
.
such that each string
is a substring
of
w
, i.e.
where
.
[
257
].
If the number of negative strings is constant, or if no negative strings
contain positive strings as substrings, the problem is approximable within
a constant [
191
].
The complementary M
AXIMUM
C
OMPRESSION
problem, where the objective is to
maximize
, is approximable within 2 [
330
]
and [
335
].
Viggo Kann