TU Berlin

Research Group Algorithmics and Computational ComplexityTalk 24.11.2011

isti-logo

Page Content

to Navigation

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.

date
speaker
location
language
24.11.2011 16:15
Christian Komusiewicz
FR 6510
german/
english*

* Language is depending on the audience.

Back to the research colloquium site.

Navigation

Quick Access

Schnellnavigation zur Seite über Nummerneingabe