On approximating string selection problems with outliers

DOI10.1016/J.TCS.2013.05.037MaRDI QIDQ391209zbMATH OpenOpenAlexFDO

Authors Christina Boucher, Gad M. Landau, Avivit Levy, David Pritchard, Oren Weimann

Publication date 10 January 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.037

zbMATH Keywords

polynomial-time approximation schemestring algorithmsstring selection

Mathematics Subject Classification ID

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

Recommendations

• On approximating string selection problems with outliers
• scientific article; zbMATH DE number 1305456
• Finding similar regions in many strings
• Distinguishing string selection problems.
• On the closest string and substring problems

Cites work

• scientific article; zbMATH DE number 1615273 (Why is no real title available?)
• scientific article; zbMATH DE number 1305511 (Why is no real title available?)
• scientific article; zbMATH DE number 6783431 (Why is no real title available?)
• A three-string approach to the closest string problem
• Algorithms – ESA 2005
• Approximate Periodicity
• Better Inapproximability Results for MaxClique, Chromatic Number and Min-3Lin-Deletion
• Closest Substring Problems with Small Distances
• Cycle detection and correction
• Detecting high log-densities, an \(O(n^{1/4})\) approximation for densest \(k\)-subgraph
• Distinguishing string selection problems.
• Efficient Algorithms for the Closest String and Distinguishing String Selection Problems
• Efficient solutions for the far from most string problem
• Finding similar regions in many sequences
• Fixed-parameter algorithms for CLOSEST STRING and related problems
• Genetic Design of Drugs Without Side-Effects
• More efficient algorithms for closest string and substring problems
• NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs
• On covering problems of codes
• On some optimization problems in molecular biology
• On the parameterized intractability of motif search problems
• Parameterized intractability of distinguishing substring selection
• Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
• Ruling Out PTAS for Graph Min‐Bisection, Dense k‐Subgraph, and Bipartite Clique
• Some optimal inapproximability results

Cited in

(4)

• Parameterized dichotomy of choosing committees based on approval votes in the presence of outliers
• On the role of metaheuristic optimization in bioinformatics
• On approximating string selection problems with outliers
• Negative selection algorithms on strings with efficient training and linear-time classification

This page was built for publication: On approximating string selection problems with outliers

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