TY - GEN
T1 - (In)approximability results for pattern matching problems
AU - Clifford, Raphaël
AU - Popa, Alexandru
PY - 2010/12/1
Y1 - 2010/12/1
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=84869143041&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84869143041&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:84869143041
SN - 9788001045978
T3 - Proceedings of the Prague Stringology Conference 2010
SP - 52
EP - 62
BT - Proceedings of the Prague Stringology Conference 2010
T2 - Prague Stringology Conference 2010, PSC 2010
Y2 - 30 August 2010 through 1 September 2010
ER -