Consensus Patterns (Probably) Has no EPTAS

DOI10.1007/978-3-662-48350-3_21zbMath1466.68089OpenAlexW2281706401MaRDI QIDQ3452789

Daniel Lokshantov, Christina Boucher, Christine Lo

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)

Related Items

The complexity of binary matrix completion under diameter constraints ⋮ Parameterized \(k\)-clustering: tractability island ⋮ Parameterized Approximation Schemes for Independent Set of Rectangles and Geometric Knapsack

Cites Work

• Unnamed Item
• Unnamed Item
• Fundamentals of parameterized complexity
• On the parameterized intractability of motif search problems
• On the parameterized complexity of multiple-interval graph problems
• Distinguishing string selection problems.
• Finding similar regions in many sequences
• Small-Bias Probability Spaces: Efficient Constructions and Applications
• Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
• Closest Substring Problems with Small Distances
• Simple Constructions of Almost k-wise Independent Random Variables
• NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs
• New Bounds for Motif Finding in Strong Instances
• Probability Inequalities for Sums of Bounded Random Variables
• Algorithms – ESA 2005
• Parameterized Algorithms
• Combinatorial Pattern Matching