Data reductions and combinatorial bounds for improved approximation algorithms

•We introduce data reduction rules for obtaining approximation algorithms for maximization problems.•These rules are combined with certain combinatorial insights often typical for kernelization algorithms.•The resulting algorithms are of a combinatorial nature, yet better than previous published wor...

Full description

Saved in:
Bibliographic Details
Published in:Journal of computer and system sciences 2016-05, Vol.82 (3), p.503-520
Main Authors: Abu-Khzam, Faisal N., Bazgan, Cristina, Chopin, Morgan, Fernau, Henning
Format: Article
Language:English
Subjects:
Computer Science
Domination problems
Maximization problems
Polynomial-time approximation
Reduction rules
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:•We introduce data reduction rules for obtaining approximation algorithms for maximization problems.•These rules are combined with certain combinatorial insights often typical for kernelization algorithms.•The resulting algorithms are of a combinatorial nature, yet better than previous published work in at least two special cases.•We discuss several concrete problems that are natural maximization versions of well-studied domination-type graph problems. Kernelization algorithms in the context of Parameterized Complexity are often based on a combination of data 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 Harmless Set, Differential and Multiple Nonblocker, all of them can be considered in the context of securing networks or information propagation.
ISSN:0022-0000
1090-2724
DOI:10.1016/j.jcss.2015.11.010