Thumbnail - No thumbnail

Data Reductions and Combinatorial Bounds for Improved Approximation Algorithms

Abu-Khzam, Faisal N.; Bazgan, Cristina; Chopin, Morgan; Fernau, Henning (2016), Data Reductions and Combinatorial Bounds for Improved Approximation Algorithms, Journal of Computer and System Sciences, 82, 3, p. 503-520. 10.1016/j.jcss.2015.11.010

Type
Article accepté pour publication ou publié
External document link
https://arxiv.org/abs/1409.3742v1
Date
2016
Journal name
Journal of Computer and System Sciences
Volume
82
Number
3
Publisher
Elsevier
Pages
503-520
Publication identifier
Metadata
Show full item record
Author(s)
Abu-Khzam, Faisal N.

Bazgan, Cristina
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Chopin, Morgan
Laboratoire d'Informatique de Paris 6 [LIP6]
Fernau, Henning
Abstract (EN)
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.
Subjects / Keywords
Parameterized complexity; Reduction rules; Maximization problems; Polynomial-time approximation; Domination problems
JEL
C44 - Operations Research; Statistical Decision Theory