On the closest string and substring problems

DOI10.1145/506147.506150zbMath1323.68635OpenAlexW2047386086MaRDI QIDQ3196639

Lusheng Wang, Bin Ma, Ming Li

Publication date: 30 October 2015

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/506147.506150

zbMATH Keywords

polynomial-time approximation schemecomputer applicationsclosest string and substring

Mathematics Subject Classification ID

Approximation algorithms (68W25) Algorithms on strings (68W32)

Related Items (38)

Configurations and minority in the string consensus problem ⋮ Constant time approximation scheme for largest well predicted subset ⋮ Near optimal solutions for maximum quasi-bicliques ⋮ On the longest common rigid subsequence problem ⋮ On the complexity of the spaced seeds ⋮ Mathematical programming formulations for the efficient solution of the \(k\)-sum approval voting problem ⋮ A combinedgreedy-walkheuristic and simulated annealing approach for the closest string problem ⋮ Mathematical programming in computational biology: an annotated bibliography ⋮ Efficient Algorithms for the Closest String and Distinguishing String Selection Problems ⋮ Polynomial time approximation schemes for all 1-center problems on metric rational set similarities ⋮ A polynomial time approximation scheme for embedding a directed hypergraph on a weighted ring ⋮ A three-string approach to the closest string problem ⋮ The k-centre problem for classes of cyclic words ⋮ On the string consensus problem and the Manhattan sequence consensus problem ⋮ Combinatorial \(n\)-fold integer programming and applications ⋮ Tight Hardness Results for Consensus Problems on Circular Strings and Time Series ⋮ A polynomial time approximation scheme for embedding hypergraph in a weighted cycle ⋮ Improved optimization modelling for the closest string and related problems ⋮ Sublinear time width-bounded separators and their application to the protein side-chain packing problem ⋮ The Fine-Grained Complexity of Median and Center String Problems Under Edit Distance ⋮ Sublinear time motif discovery from multiple sequences ⋮ Parameterized complexity analysis for the closest string with wildcards problem ⋮ Separating sets of strings by finding matching patterns is almost always hard ⋮ A polynomial time approximation scheme for the closest shared center problem ⋮ On the kernelization complexity of string problems ⋮ Low-Rank Binary Matrix Approximation in Column-Sum Norm. ⋮ An improved lower bound on approximation algorithms for the closest substring problem ⋮ A GRASP algorithm for the closest string problem using a probability-based heuristic ⋮ A heuristic algorithm based on Lagrangian relaxation for the closest string problem ⋮ A parallel multistart algorithm for the closest string problem ⋮ Listing Center Strings Under the Edit Distance Metric ⋮ Slightly Superexponential Parameterized Problems ⋮ Exact algorithm and heuristic for the closest string problem ⋮ Efficient algorithms for consensus string problems minimizing both distance sum and radius ⋮ A polynomial time approximation scheme for embedding a directed hypergraph on a ring ⋮ Hardness results for the center and median string problems under the weighted and unweighted edit distances ⋮ Finding similar regions in many sequences ⋮ Randomized fixed-parameter algorithms for the closest string problem

This page was built for publication: On the closest string and substring problems