Approximation algorithms inspired by Kernelization methods

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

Research output: Chapter in Book/Report/Conference proceedingConference Paper published in Proceedingspeer-review

1 Downloads (Pure)


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 notionof 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
Title of host publicationAlgorithms and Computation, 25th International Symposium, ISAAC 2014, Jeonju, Korea, December 15-17, 2014, Proceedings, Lecture Notes in Computer Science Vol 8889
EditorsHK Ahn, CS Shin
Place of PublicationSwitzerland
Number of pages12
ISBN (Print)978-3-319-13074-3
Publication statusPublished - 2014
Externally publishedYes
EventInternational Symposium on Algorithms and Computation (ISAAC 2014 25th) - Jeonju, Korea, Jeonju, Korea, Republic of
Duration: 15 Dec 201417 Dec 2014
Conference number: 2014 (25th)

Publication series

NameLecture Notes in Computer Science
ISSN (Print)0302-9743


ConferenceInternational Symposium on Algorithms and Computation (ISAAC 2014 25th)
Abbreviated titleISAAC
Country/TerritoryKorea, Republic of


Dive into the research topics of 'Approximation algorithms inspired by Kernelization methods'. Together they form a unique fingerprint.

Cite this