Local search for string problems: brute-force is essentially optimal

DOI10.1016/J.TCS.2013.05.006MaRDI QIDQ2437744zbMATH OpenOpenAlexFDO

Authors Jiong Guo, Danny Hermelin, Christian Komusiewicz

Publication date 13 March 2014

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2013.05.006

zbMATH Keywords

local searchlongest common subsequenceparameterized complexityshortest common superstringshortest common supersequenceparameterized intractabilityclosest string

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Algorithms on strings (68W32)

Recommendations

• Local search for string problems: brute force is essentially optimal
• Consequences of Faster Alignment of Sequences
• Maximal common subsequences and minimal common supersequences
• scientific article; zbMATH DE number 827942
• Automata, Languages and Programming

Cites work

• scientific article; zbMATH DE number 1082099 (Why is no real title available?)
• scientific article; zbMATH DE number 1161563 (Why is no real title available?)
• Efficient solutions for the far from most string problem
• Fixed-parameter algorithms for CLOSEST STRING and related problems
• How easy is local search?
• Lower bounds based on the exponential time hypothesis
• New classes of efficiently solvable generalized traveling salesman problems
• On the hardness of losing weight
• On the parameterized complexity of consensus clustering
• Searching the \(k\)-change neighborhood for TSP is W[1]-hard
• Stable assignment with couples: parameterized complexity and local search
• The parameterized complexity of \(k\)-flip local search for SAT and MAX SAT
• The parameterized complexity of local search for TSP, more refined
• Tight lower bounds for certain parameterized NP-hard problems

Cited in

(3)

• Local search for string problems: brute force is essentially optimal
• Polynomial time approximation schemes for all 1-center problems on metric rational set similarities
• String editing under pattern constraints

This page was built for publication: Local search for string problems: brute-force is essentially optimal

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2437744)