direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Page Content

On Parameterized Local Search for Closest String

Christian Komusiewicz (TU Berlin)

We study the parameterized complexity of local search variants for the NP-hard Closest String problem. Herein, one is given a set S of strings and distinguished string s with Hamming distance at most d to each string in S and asks whether there is a "better" string s' within Hamming distance k from s such that s' has Hamming distance at most d'<d to each string in S. Our main result is that this problem is W[1]-hard for k even in the case of binary alphabet. We also report on preliminary results for Local Search variants of other NP-hard string problems.

24.11.2011 16:15
Christian Komusiewicz
FR 6510

* Language is depending on the audience.

Back to the research colloquium site.

Zusatzinformationen / Extras