Data reductions and combinatorial bounds for improved approximation algorithms

Faisal Abu Khzam, Cristina Bazgan, Morgan Chopin, Henning Fernau

Research output: Contribution to journalArticle

2 Downloads (Pure)

Abstract

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.
Original languageEnglish
Pages (from-to)503-520
Number of pages18
JournalJournal of Computer and System Sciences
Volume82
Issue number3
DOIs
Publication statusPublished - May 2016
Externally publishedYes

Fingerprint Dive into the research topics of 'Data reductions and combinatorial bounds for improved approximation algorithms'. Together they form a unique fingerprint.

  • Cite this