Prague Stringology Conference 2010

Raphaël Clifford and Alexandru Popa

(In)approximability Results for Pattern Matching Problems

Abstract:
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 article: Article in PostScript Article in PDF BibTeX Reference
 PostScript   PDF   BibTeX reference