We study the complexity of the problem of searching for a set of patterns that separate two given sets of strings. This problem has applications in a wide variety of areas, most notably in data mining, computational biology, and in understanding the complexity of genetic algorithms. We show that the basic problem of finding a small set of patterns that match one set of strings but do not match any string in a second set is difficult (NP-complete, W[2]-hard when parameterized by the size of the pattern set, and APX-hard). We then perform a detailed parameterized analysis of the problem, separating tractable and intractable variants. In particular we show that parameterizing by the size of pattern set and the number of strings, and the size of the alphabet and the number of strings give FPT results, amongst others.
@cite_12: We introduce the class cover problem, a variant of disk cover with forbidden regions, with applications to classification and facility location problems. We prove similar hardness results to disk cover. We then present a polynomial-time approximation algorithm for class cover that performs within a ln n+1 factor of optimal, which is nearly tight under standard hardness assumptions. In the special case that the points lie in a d-dimensional space with Euclidean norm, for some fixed constant d, we obtain a polynomial time approximation scheme.
Introduced by Cannon and Cowen @cite_12 , the problem is a geometric relative of where the input is two sets of points colored red and blue, with the goal of selecting a minimum set of blue points (centers) that cover'' the full set of blue points, in the sense that any blue point is closer to its nearest center than any red point. It is -hard with an @math -factor approximation algorithm, bearing a close similarity to .