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: | |||

PostScript | BibTeX reference |