Parameterized Approximation Problems

DOI10.1007/11847250_11zbMath1154.68572MaRDI 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

68Q25: Analysis of algorithms and problem complexity

68W25: Approximation algorithms

Related Items

Moderately Exponential Approximation: Bridging the Gap Between Exact Computation and Polynomial Approximation, The Constant Inapproximability of the Parameterized Dominating Set Problem, Parameterized Approximation Schemes for Independent Set of Rectangles and Geometric Knapsack, Backdoors to q-Horn, An exponential time 2-approximation algorithm for bandwidth, Exponential approximation schemata for some network design problems, Approximation of max independent set, min vertex cover and related problems by moderately exponential algorithms, Confronting intractability via parameters, Approximating MAX SAT by moderately exponential and parameterized algorithms, Efficient algorithms for the \textsc{max~\(k\)-vertex cover problem}, On the max min vertex cover problem, 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, Exact and superpolynomial approximation algorithms for the \textsc{densest \textit{K}-subgraph} problem, 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, Finding hidden hubs and dominating sets in sparse graphs by randomized neighborhood queries, Efficient Approximation of Combinatorial Problems by Moderately Exponential Algorithms