Data reductions and combinatorial bounds for improved approximation algorithms
From MaRDI portal
Publication:899583
DOI10.1016/J.JCSS.2015.11.010zbMATH Open1333.68290arXiv1409.3742OpenAlexW135432853WikidataQ59864893 ScholiaQ59864893MaRDI QIDQ899583FDOQ899583
Faisal N. Abu-Khzam, Henning Fernau, Morgan Chopin, Cristina Bazgan
Publication date: 30 December 2015
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1409.3742
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Fundamentals of parameterized complexity
- LP can be a cure for parameterized problems
- The Robust Set Problem: Parameterized Complexity and Approximation
- Extremal Problems for Roman Domination
- Total Domination in Graphs
- Upper bounds on the \(k\)-domination number and the \(k\)-Roman domination number
- Computing the differential of a graph: hardness, approximability and exact algorithms
- Enclaveless sets and MK-Systems
- Combinatorics for smaller kernels: the differential of a graph
- On the Equivalence between the Primal-Dual Schema and the Local Ratio Technique
- Lower bounds on the differential of a graph
- Domination in graphs with minimum degree two
- Paths, Stars and the Number Three
- An upper bound for thek-domination number of a graph
- Parameterized Approximation Algorithms for Hitting Set
- ROMAN k-DOMINATION IN GRAPHS
- R<scp>OMAN DOMINATION</scp>: a parameterized perspective†
- SOFSEM 2006: Theory and Practice of Computer Science
- Approximation hardness of dominating set problems in bounded degree graphs
- The differential and the roman domination number of a graph
- Roman domination on 2-connected graphs
- Upper bounds on Roman domination numbers of graphs
- A novel parameterised approximation algorithm for \textsc{minimum vertex cover}
- A note on the k-domination number of a graph
- COMPLETENESS IN DIFFERENTIAL APPROXIMATION CLASSES
- Improved approximation algorithms for the spanning star forest problem
- An Improved Approximation Bound for Spanning Star Forest and Color Saving
- Approximating the Spanning Star Forest Problem and Its Application to Genomic Sequence Alignment
- Generalized independence and domination in graphs
- Relations between the Roman \(k\)-domination and Roman domination numbers in graphs
- Approximation Algorithms Inspired by Kernelization Methods
Cited In (10)
- Title not available (Why is that?)
- Data reduction and exact algorithms for clique cover
- Minimal Roman dominating functions: extensions and enumeration
- Domination chain: characterisation, classical complexity, parameterised complexity and approximability
- Knapsack problems: a parameterized point of view
- Parameterized approximation via fidelity preserving transformations
- Polynomial-time data reduction for weighted problems beyond additive goal functions
- Algorithmic Aspects of Upper Domination: A Parameterised Perspective
- The many facets of upper domination
- Minimal Roman dominating functions: extensions and enumeration
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)
