(In)approximability results for pattern matching problems

Raphaël Clifford, Alexandru Popa

Research output: Chapter in Book/Report/Conference proceedingConference contribution

3 Citations (Scopus)

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 languageEnglish
Title of host publicationProceedings of the Prague Stringology Conference 2010
Pages52-62
Number of pages11
Publication statusPublished - Dec 1 2010
EventPrague Stringology Conference 2010, PSC 2010 - Prague, Czech Republic
Duration: Aug 30 2010Sep 1 2010

Publication series

NameProceedings of the Prague Stringology Conference 2010

Other

OtherPrague Stringology Conference 2010, PSC 2010
CountryCzech Republic
CityPrague
Period8/30/109/1/10

ASJC Scopus subject areas

  • Mathematics(all)

Fingerprint Dive into the research topics of '(In)approximability results for pattern matching problems'. Together they form a unique fingerprint.

  • Cite this

    Clifford, R., & Popa, A. (2010). (In)approximability results for pattern matching problems. In Proceedings of the Prague Stringology Conference 2010 (pp. 52-62). (Proceedings of the Prague Stringology Conference 2010).