(In)approximability results for pattern matching problems

Raphaël Clifford, Alexandru Popa

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

2 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 - 2010
Externally publishedYes
EventPrague Stringology Conference 2010, PSC 2010 - Prague, Czech Republic
Duration: Aug 30 2010Sep 1 2010

Other

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

Fingerprint

Inapproximability
Pattern Matching
Matching Problem
Approximation Algorithms
Polynomial time
Strings
Approximability
Generalized Functions
Subsequence
NP-complete problem
Approximation

ASJC Scopus subject areas

  • Mathematics(all)

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)

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

Proceedings of the Prague Stringology Conference 2010. 2010. p. 52-62.

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

Clifford, R & Popa, A 2010, (In)approximability results for pattern matching problems. in Proceedings of the Prague Stringology Conference 2010. pp. 52-62, Prague Stringology Conference 2010, PSC 2010, Prague, Czech Republic, 8/30/10.
Clifford R, Popa A. (In)approximability results for pattern matching problems. In Proceedings of the Prague Stringology Conference 2010. 2010. p. 52-62
Clifford, Raphaël ; Popa, Alexandru. / (In)approximability results for pattern matching problems. Proceedings of the Prague Stringology Conference 2010. 2010. pp. 52-62
@inproceedings{93bb1abe3bd440f5ac5c6583cbcad4b9,
title = "(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.",
author = "Rapha{\"e}l Clifford and Alexandru Popa",
year = "2010",
language = "English",
isbn = "9788001045978",
pages = "52--62",
booktitle = "Proceedings of the Prague Stringology Conference 2010",

}

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

SN - 9788001045978

SP - 52

EP - 62

BT - Proceedings of the Prague Stringology Conference 2010

ER -