On Parameterized Approximability

DOI10.1007/11847250_10zbMath1154.68571OpenAlexW1492330052MaRDI 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

Analysis of algorithms and problem complexity (68Q25) Approximation methods and heuristics in mathematical programming (90C59) Approximation algorithms (68W25)

Related Items (28)

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

This page was built for publication: On Parameterized Approximability