Parameterized Approximation Problems

DOI10.1007/11847250_11zbMath1154.68572OpenAlexW1516574938MaRDI QIDQ3499730

Catherine McCartin, Michael R. Fellows, Rodney G. Downey

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_11

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25)

Related Items (28)

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 ⋮ Exact and superpolynomial approximation algorithms for the \textsc{densest \textit{K}-subgraph} problem ⋮ Exponential approximation schemata for some network design problems ⋮ 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 ⋮ Sparsification and subexponential approximation ⋮ Dual parameterization and parameterized approximability of subset graph problems ⋮ Fixed-parameter algorithms for unsplittable flow cover ⋮ Confronting intractability via parameters ⋮ Approximating MAX SAT by moderately exponential and parameterized algorithms ⋮ The Constant Inapproximability of the Parameterized Dominating Set Problem ⋮ Efficient algorithms for the \textsc{max~\(k\)-vertex cover problem} ⋮ Improved Approximations for Hard Optimization Problems via Problem Instance Classification ⋮ On the max min vertex cover problem ⋮ 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 ⋮ Finding hidden hubs and dominating sets in sparse graphs by randomized neighborhood queries ⋮ Efficient approximation of Min Set Cover by moderately exponential algorithms ⋮ On subexponential and FPT-time inapproximability ⋮ Moderately exponential time and fixed parameter approximation algorithms ⋮ Backdoors to q-Horn

This page was built for publication: Parameterized Approximation Problems