
Approximation Algorithms Inspired by Kernelization Methods
Abu-Khzam, Faisal N.; Bazgan, Cristina; Chopin, Morgan; Fernau, Henning (2014), Approximation Algorithms Inspired by Kernelization Methods, in Ahn, Hee-Kap; Shin, Chan-Su, Algorithms and Computation, Springer : Cham, p. 479-490. 10.1007/978-3-319-13075-0_38
View/ Open
Type
Communication / ConférenceDate
2014Conference title
25th International Symposium, ISAAC 2014Conference date
2014-12Conference city
JeonjuConference country
South KoreaBook title
Algorithms and ComputationBook author
Ahn, Hee-Kap; Shin, Chan-SuPublisher
Springer
Published in
Cham
ISBN
978-3-319-13074-3
Number of pages
781Pages
479-490
Publication identifier
Metadata
Show full item recordAuthor(s)
Abu-Khzam, Faisal N.Lebanese American University [LAU]
Bazgan, Cristina
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Chopin, Morgan
Institut für Optimierung und Operations Research
Fernau, Henning
Abstract (EN)
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 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; approximationRelated items
Showing items related by title and author.
-
Abu-Khzam, Faisal N.; Bazgan, Cristina; Chopin, Morgan; Fernau, Henning (2016) Article accepté pour publication ou publié
-
Abu-Khzam, Faisal N.; Bazgan, Cristina; Casel, Katrin; Fernau, Henning (2016) Communication / Conférence
-
Abu-Khzam, Faisal N.; Bazgan, Cristina; Casel, Katrin; Fernau, Henning (2018) Article accepté pour publication ou publié
-
Abu-Khzam, Faisal; Bazgan, Cristina; Fernau, Henning (2020) Communication / Conférence
-
Abu-Khzam, Faisal N.; Bazgan, Cristina; El Haddad, Joyce; Sikora, Florian (2015) Communication / Conférence