Consensus patterns (probably) has no EPTAS

DOI10.1007/978-3-662-48350-3_21MaRDI QIDQ3452789zbMATH OpenOpenAlexFDO

Authors Christina Boucher, Christine Lo, Daniel Lokshantov

Publication date 19 November 2015

Published in Algorithms - ESA 2015 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-662-48350-3_21

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Algorithms on strings (68W32) Parameterized complexity, tractability and kernelization (68Q27)

Recommendations

• Combinatorial Pattern Matching
• Lower bounds for approximation schemes for Closest String
• Combinatorial Pattern Matching
• On the parameterized intractability of motif search problems
• Finding consensus strings with small length difference between input and solution strings

Cites work

• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• Algorithms – ESA 2005
• Closest Substring Problems with Small Distances
• Combinatorial Pattern Matching
• Distinguishing string selection problems.
• Finding similar regions in many sequences
• Fundamentals of parameterized complexity
• NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs
• New Bounds for Motif Finding in Strong Instances
• On the parameterized complexity of multiple-interval graph problems
• On the parameterized intractability of motif search problems
• Parameterized algorithms
• Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
• Probability Inequalities for Sums of Bounded Random Variables
• Probability and random processes.
• Simple Constructions of Almost k-wise Independent Random Variables
• Small-Bias Probability Spaces: Efficient Constructions and Applications

Cited in

(6)

• Matrix completion: approximating the minimum diameter
• Finding similar regions in many sequences
• Parameterized \(k\)-clustering: tractability island
• Parameterized Approximation Schemes for Independent Set of Rectangles and Geometric Knapsack
• Combinatorial Pattern Matching
• The complexity of binary matrix completion under diameter constraints

This page was built for publication: Consensus patterns (probably) has no EPTAS

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