Prague Stringology Conference 2010

Raphaël Clifford and Alexandru Popa

(In)approximability Results for Pattern Matching Problems

We consider the approximability of three recently introduced pattern matching problems which have been shown to be NP-hard. Given two strings as input, the first problem is to find the longest common parameterised subsequence between two strings. The second is a maximisation variant of generalised function matching and the third is a a maximisation variant of generalised parameterised matching. We show that in all three cases there exists an ε > 0 such that there is no polynomial time (1-ε)-approximation algorithm, unless P = NP. We then present a polynomial time √(1/OPT)-approximation algorithm for a variant of generalised parameterised matching for which no previous approximation results are known.

Download paper: Article in PostScript Article in PDF BibTeX Reference
 PostScript   PDF   BibTeX reference