Parameterized approximation via fidelity preserving transformations
From MaRDI portal
Publication:1686226
DOI10.1016/j.jcss.2017.11.001zbMath1382.68105MaRDI QIDQ1686226
Ariel Kulik, Michael R. Fellows, Hadas Shachnai, Frances A. Rosamond
Publication date: 21 December 2017
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jcss.2017.11.001
fixed parameter tractability; approximation algorithms; parameterized complexity; kernelization; fidelity-preserving transformation
Related Items
Parameterized algorithms and data reduction for the short secluded s‐t‐path problem, Dynamic kernels for hitting sets and set packing, Invited talks
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Fundamentals of parameterized complexity
- 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
- Exact exponential algorithms.
- Exact and approximate bandwidth
- Improved upper bounds for vertex cover
- There is no EPTAS for two-dimensional knapsack
- Data reductions and combinatorial bounds for improved approximation algorithms
- Parameterized approximation of dominating set problems
- A kernelization algorithm for \(d\)-hitting set
- Exponential-time approximation of weighted set cover
- Constant ratio fixed-parameter approximation of the edge multicut problem
- On the existence of subexponential parameterized algorithms
- One for the price of two: a unified approach for approximating covering problems
- Fixed-parameter approximation: conceptual framework and approximability results
- Approximation and tidying -- a problem kernel for \(s\)-plex cluster vertex deletion
- Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
- A $c^k n$ 5-Approximation Algorithm for Treewidth
- Parameterized Approximation via Fidelity Preserving Transformations
- Saving on Phases: Parameterized Approximation for Total Vertex Cover
- Parameterized Approximation Algorithms for Hitting Set
- Deterministic Parameterized Connected Vertex Cover
- An approximation algorithm for the maximum leaf spanning arborescence problem
- The Design of Approximation Algorithms
- On Parameterized Approximability
- Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
- Fourier meets M\"{o}bius: fast subset convolution
- Set Partitioning via Inclusion-Exclusion
- Confronting hardness using a hybrid approach
- Parameterized Approximation Scheme for the Multiple Knapsack Problem
- Lossy kernelization
- An EPTAS for Scheduling Jobs on Uniform Processors: Using an MILP Relaxation with a Constant Number of Integral Variables
- Parameterized Approximability of the Disjoint Cycle Problem
- The steiner problem in graphs
