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 Proceedings

1 Downloads (Pure)

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 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
PublisherSpringer
Pages479-490
Number of pages12
Edition1
ISBN (Print)978-3-319-13074-3
DOIs
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
PublisherSpringer
Volume8889
ISSN (Print)0302-9743

Conference

ConferenceInternational Symposium on Algorithms and Computation (ISAAC 2014 25th)
Abbreviated titleISAAC
CountryKorea, Republic of
CityJeonju
Period15/12/1417/12/14

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

  • Cite this

    Abu Khzam, F., Bazgan, C., Chopin, M., & Fernau, H. (2014). Approximation algorithms inspired by Kernelization methods. In HK. Ahn, & CS. Shin (Eds.), Algorithms and Computation, 25th International Symposium, ISAAC 2014, Jeonju, Korea, December 15-17, 2014, Proceedings, Lecture Notes in Computer Science Vol 8889 (1 ed., pp. 479-490). (Lecture Notes in Computer Science; Vol. 8889). Springer. https://doi.org/10.1007/978-3-319-13075-0_38