### 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.

Original language | English |
---|---|

Title of host publication | Proceedings of the Prague Stringology Conference 2010 |

Pages | 52-62 |

Number of pages | 11 |

Publication status | Published - 2010 |

Externally published | Yes |

Event | Prague Stringology Conference 2010, PSC 2010 - Prague, Czech Republic Duration: Aug 30 2010 → Sep 1 2010 |

### Other

Other | Prague Stringology Conference 2010, PSC 2010 |
---|---|

Country | Czech Republic |

City | Prague |

Period | 8/30/10 → 9/1/10 |

### Fingerprint

### ASJC Scopus subject areas

- Mathematics(all)

### Cite this

*Proceedings of the Prague Stringology Conference 2010*(pp. 52-62)

**(In)approximability results for pattern matching problems.** / Clifford, Raphaël; Popa, Alexandru.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

*Proceedings of the Prague Stringology Conference 2010.*pp. 52-62, Prague Stringology Conference 2010, PSC 2010, Prague, Czech Republic, 8/30/10.

}

TY - GEN

T1 - (In)approximability results for pattern matching problems

AU - Clifford, Raphaël

AU - Popa, Alexandru

PY - 2010

Y1 - 2010

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

SP - 52

EP - 62

BT - Proceedings of the Prague Stringology Conference 2010

ER -