On Parameterized Approximability

DOI10.1007/11847250_10zbMath1154.68571MaRDI QIDQ3499729

Yijia Chen, Magdalena Grüber, Martin Grohe

Publication date: 3 June 2008

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

Full work available at URL: https://doi.org/10.1007/11847250_10

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

90C59: Approximation methods and heuristics in mathematical programming

68W25: Approximation algorithms

Related Items

Moderately Exponential Approximation: Bridging the Gap Between Exact Computation and Polynomial Approximation, From Gap-Exponential Time Hypothesis to Fixed Parameter Tractable Inapproximability: Clique, Dominating Set, and More, Parameterized Approximation Schemes for Independent Set of Rectangles and Geometric Knapsack, An exponential time 2-approximation algorithm for bandwidth, A novel parameterised approximation algorithm for \textsc{minimum vertex cover}, Approximation of max independent set, min vertex cover and related problems by moderately exponential algorithms, Confronting intractability via parameters, On the max min vertex cover problem, List H-coloring a graph by removing few vertices, Parameterized approximation of dominating set problems, Constant ratio fixed-parameter approximation of the edge multicut problem, Parameterizing above or below guaranteed values, Efficient approximation of Min Set Cover by moderately exponential algorithms, Finding disjoint paths on edge-colored graphs: more tractability results, Parameterized approximation via fidelity preserving transformations, Sparsification and subexponential approximation, Parameterized (in)approximability of subset problems, On subexponential and FPT-time inapproximability, Fixed-parameter approximation: conceptual framework and approximability results, Fixed-parameter algorithms for unsplittable flow cover, Moderately exponential time and fixed parameter approximation algorithms, Backdoors to Satisfaction, Super-polynomial approximation branching algorithms, Parameterized exact and approximation algorithms for maximumk-set cover and related satisfiability problems, Dual parameterization and parameterized approximability of subset graph problems, Improved Approximations for Hard Optimization Problems via Problem Instance Classification, Efficient Approximation of Combinatorial Problems by Moderately Exponential Algorithms