On subexponential and FPT-time inapproximability

DOI10.1007/s00453-014-9889-1zbMath1312.68232arXiv1211.6656OpenAlexW2029910715MaRDI QIDQ2343081

Eun Jung Kim, Édouard Bonnet, Vangelis Th. Paschos, Bruno Escoffier

Publication date: 4 May 2015

Published in: Algorithmica, Parameterized and Exact Computation (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1211.6656

zbMATH Keywords

inapproximabilitysubexponential timeAPETHFPT-time

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25)

Related Items (14)

Fixed Parameter Approximations for k-Center Problems in Low Highway Dimension Graphs ⋮ Unnamed Item ⋮ Super-polynomial approximation branching algorithms ⋮ From Gap-Exponential Time Hypothesis to Fixed Parameter Tractable Inapproximability: Clique, Dominating Set, and More ⋮ Sparsification and subexponential approximation ⋮ When polynomial approximation meets exact computation ⋮ ETH-Hardness of Approximating 2-CSPs and Directed Steiner Network ⋮ The Constant Inapproximability of the Parameterized Dominating Set Problem ⋮ When polynomial approximation meets exact computation ⋮ Unnamed Item ⋮ Minimum fill-in: inapproximability and almost tight lower bounds ⋮ Upper dominating set: tight algorithms for pathwidth and sub-exponential approximation ⋮ Upper dominating set: tight algorithms for pathwidth and sub-exponential approximation ⋮ Moderate exponential-time algorithms for scheduling problems

Cites Work

• Unnamed Item
• Unnamed Item
• An exponential time 2-approximation algorithm for bandwidth
• Approximation of max independent set, min vertex cover and related problems by moderately exponential algorithms
• Exact and approximate bandwidth
• Strong computational lower bounds via parameterized complexity
• Parameterized approximation of dominating set problems
• Approximation of min coloring by moderately exponential algorithms
• Explicit constructions of linear-sized superconcentrators
• Optimization, approximation, and complexity classes
• On approximation algorithms for the minimum satisfiability problem
• On fixed-parameter tractability and approximability of NP optimization problems
• Which problems have strongly exponential complexity?
• Entropy waves, the zig-zag graph product, and new constant-degree expanders
• Parameterized (in)approximability of subset problems
• On the existence of subexponential parameterized algorithms
• Fixed-parameter approximation: conceptual framework and approximability results
• Fixed-Parameter and Approximation Algorithms: A New Look
• Improved Parameterized Algorithms for above Average Constraint Satisfaction
• Safe Approximation and Its Relation to Kernelization
• Approximating MAX SAT by Moderately Exponential and Parameterized Algorithms
• Proof verification and the hardness of approximation problems
• On Approximate Solutions for Combinatorial Optimization Problems
• On Parameterized Approximability
• Parameterized Approximation Problems
• Expander graphs and their applications
• Set Partitioning via Inclusion-Exclusion
• Two-query PCP with subconstant error
• On the hardness of approximating minimization problems
• The PCP theorem by gap amplification

This page was built for publication: On subexponential and FPT-time inapproximability