• français
    • English
  • français 
    • français
    • English
  • Login
JavaScript is disabled for your browser. Some features of this site may not work without it.
BIRD Home

Browse

This CollectionBy Issue DateAuthorsTitlesSubjectsJournals BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesSubjectsJournals

My Account

Login

Statistics

View Usage Statistics

Approximation Algorithms Inspired by Kernelization Methods

Thumbnail
View/Open
approximation.pdf (333.1Kb)
Date
2014
Notes
in Lecture Notes in Computer Science, vol. 8889
Dewey
Recherche opérationnelle
Sujet
parameterized complexity; approximation
JEL code
C.C4.C44
DOI
http://dx.doi.org/10.1007/978-3-319-13075-0_38
Conference name
25th International Symposium, ISAAC 2014
Conference date
12-2014
Conference city
Jeonju
Conference country
South Korea
Book title
Algorithms and Computation
Author
Ahn, Hee-Kap; Shin, Chan-Su
Publisher
Springer
Publisher city
Cham
Year
2014
Pages number
781
ISBN
978-3-319-13074-3
Book URL
10.1007/978-3-319-13075-0
URI
https://basepub.dauphine.fr/handle/123456789/16162
Collections
  • LAMSADE : Publications
Metadata
Show full item record
Author
Abu-Khzam, Faisal N.
status unknown
Bazgan, Cristina
989 Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Chopin, Morgan
215382 Institut für Optimierung und Operations Research
Fernau, Henning
status unknown
Type
Communication / Conférence
Item number of pages
479-490
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.

  • Accueil Bibliothèque
  • Site de l'Université Paris-Dauphine
  • Contact
SCD Paris Dauphine - Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16

 Content on this site is licensed under a Creative Commons 2.0 France (CC BY-NC-ND 2.0) license.