• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesTypeThis CollectionBy Issue DateAuthorsTitlesType

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors
Thumbnail

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
approximation.pdf (333.1Kb)
Type
Communication / Conférence
Date
2014
Conference title
25th International Symposium, ISAAC 2014
Conference date
2014-12
Conference city
Jeonju
Conference country
South Korea
Book title
Algorithms and Computation
Book author
Ahn, Hee-Kap; Shin, Chan-Su
Publisher
Springer
Published in
Cham
ISBN
978-3-319-13074-3
Number of pages
781
Pages
479-490
Publication identifier
10.1007/978-3-319-13075-0_38
Metadata
Show full item record
Author(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; approximation
JEL
C44 - Operations Research; Statistical Decision Theory

Related items

Showing items related by title and author.

  • Thumbnail
    Data Reductions and Combinatorial Bounds for Improved Approximation Algorithms 
    Abu-Khzam, Faisal N.; Bazgan, Cristina; Chopin, Morgan; Fernau, Henning (2016) Article accepté pour publication ou publié
  • Thumbnail
    Building Clusters with Lower-Bounded Sizes 
    Abu-Khzam, Faisal N.; Bazgan, Cristina; Casel, Katrin; Fernau, Henning (2016) Communication / Conférence
  • Thumbnail
    Clustering with Lower-Bounded Sizes - A General Graph-Theoretic Framework 
    Abu-Khzam, Faisal N.; Bazgan, Cristina; Casel, Katrin; Fernau, Henning (2018) Article accepté pour publication ou publié
  • Thumbnail
    Parameterized Dynamic Variants of Red-Blue Dominating Set 
    Abu-Khzam, Faisal; Bazgan, Cristina; Fernau, Henning (2020) Communication / Conférence
  • Thumbnail
    On the Complexity of QoS-Aware Service Selection Problem 
    Abu-Khzam, Faisal N.; Bazgan, Cristina; El Haddad, Joyce; Sikora, Florian (2015) Communication / Conférence
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Phone: 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo