Data reductions and combinatorial bounds for improved approximation algorithms
From MaRDI portal
Publication:899583
Abstract: Kernelization algorithms in the context of Parameterized Complexity are often based on a combination of reduction rules and combinatorial insights. We will expose in this paper a similar strategy for obtaining polynomial-time approximation algorithms. Our method features the use of approximation-preserving reductions, akin to the notion of parameterized reductions. We exemplify this method to obtain the currently best approximation algorithms for extsc{Harmless Set}, extsc{Differential} and extsc{Multiple Nonblocker}, all of them can be considered in the context of securing networks or information propagation.
Recommendations
- Approximation algorithms inspired by kernelization methods
- Combining Two Worlds: Parameterised Approximation for Vertex Cover
- Fixed-Parameter Approximation: Conceptual Framework and Approximability Results
- Lossy kernelization
- Fixed-parameter approximation: conceptual framework and approximability results
Cites work
- scientific article; zbMATH DE number 5725105 (Why is no real title available?)
- scientific article; zbMATH DE number 3914370 (Why is no real title available?)
- scientific article; zbMATH DE number 1330033 (Why is no real title available?)
- scientific article; zbMATH DE number 1341905 (Why is no real title available?)
- scientific article; zbMATH DE number 1095171 (Why is no real title available?)
- scientific article; zbMATH DE number 1559563 (Why is no real title available?)
- A note on the k-domination number of a graph
- A novel parameterised approximation algorithm for \textsc{minimum vertex cover}
- An Improved Approximation Bound for Spanning Star Forest and Color Saving
- An upper bound for thek-domination number of a graph
- Approximating the Spanning Star Forest Problem and Its Application to Genomic Sequence Alignment
- Approximation algorithms inspired by kernelization methods
- Approximation hardness of dominating set problems in bounded degree graphs
- COMPLETENESS IN DIFFERENTIAL APPROXIMATION CLASSES
- Combinatorics for smaller kernels: the differential of a graph
- Computing the differential of a graph: hardness, approximability and exact algorithms
- Differentials in graphs
- Domination in graphs with minimum degree two
- Enclaveless sets and MK-Systems
- Extremal problems for roman domination
- Fundamentals of parameterized complexity
- Generalized independence and domination in graphs
- Improved approximation algorithms for the spanning star forest problem
- LP can be a cure for parameterized problems
- Lower bounds on the differential of a graph
- On the Equivalence between the Primal-Dual Schema and the Local Ratio Technique
- On the total domination number of graphs
- Parameterized approximation algorithms for hitting set
- Paths, Stars and the Number Three
- R<scp>OMAN DOMINATION</scp>: a parameterized perspective†
- Relations between the Roman \(k\)-domination and Roman domination numbers in graphs
- Roman \(k\)-domination in graphs
- Roman domination on 2-connected graphs
- SOFSEM 2006: Theory and Practice of Computer Science
- The differential and the roman domination number of a graph
- The robust set problem: parameterized complexity and approximation
- Total domination in graphs
- Upper bounds on Roman domination numbers of graphs
- Upper bounds on the \(k\)-domination number and the \(k\)-Roman domination number
Cited in
(11)- Algorithmic aspects of \textsc{Upper Domination}: a parameterised perspective
- Knapsack problems: a parameterized point of view
- Minimal Roman dominating functions: extensions and enumeration
- Polynomial-time data reduction for weighted problems beyond additive goal functions
- Parameterized approximation via fidelity preserving transformations
- Data reduction and exact algorithms for clique cover
- Domination chain: characterisation, classical complexity, parameterised complexity and approximability
- The many facets of upper domination
- Approximation algorithms inspired by kernelization methods
- Minimal Roman dominating functions: extensions and enumeration
- scientific article; zbMATH DE number 3974286 (Why is no real title available?)
This page was built for publication: Data reductions and combinatorial bounds for improved approximation algorithms
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q899583)
