Fixed-Parameter Approximation: Conceptual Framework and Approximability Results
From MaRDI portal
Publication:3499727
DOI10.1007/11847250_9zbMath1154.68570MaRDI QIDQ3499727
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_9
Related Items
Moderately Exponential Approximation: Bridging the Gap Between Exact Computation and Polynomial Approximation, Parameterized Approximation Schemes for Independent Set of Rectangles and Geometric Knapsack, 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, 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, Exact and superpolynomial approximation algorithms for the \textsc{densest \textit{K}-subgraph} problem, Sparsification and subexponential approximation, Parameterized (in)approximability of subset problems, New results on polynomial inapproximability and fixed parameter approximability of Edge Dominating Set, Fixed-parameter algorithms for unsplittable flow cover, Moderately exponential time and fixed parameter approximation algorithms, 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, Efficient Approximation of Combinatorial Problems by Moderately Exponential Algorithms
