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 paper: |  |
 |
 |
| PostScript | BibTeX reference |