Show simple item record

dc.contributor.authorAbu-Khzam, Faisal*
dc.contributor.authorBazgan, Cristina*
dc.contributor.authorChopin, Morgan*
dc.contributor.authorFernau, Henning*
dc.date.accessioned2017-01-16T10:30:16Z
dc.date.available2017-01-16T10:30:16Z
dc.date.issued2014
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/16162
dc.descriptionin Lecture Notes in Computer Science, vol. 8889en
dc.language.isoenen
dc.subjectparameterized complexityen
dc.subjectapproximationen
dc.subject.ddc003en
dc.subject.classificationjelC.C4.C44en
dc.titleApproximation Algorithms Inspired by Kernelization Methodsen
dc.typeCommunication / Conférence
dc.description.abstractenKernelization 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.en
dc.identifier.citationpages479-490en
dc.relation.ispartoftitleAlgorithms and Computationen
dc.relation.ispartofeditorAhn, Hee-Kap
dc.relation.ispartofeditorShin, Chan-Su
dc.relation.ispartofpublnameSpringeren
dc.relation.ispartofpublcityChamen
dc.relation.ispartofdate2014
dc.relation.ispartofpages781en
dc.relation.ispartofurl10.1007/978-3-319-13075-0en
dc.contributor.countryeditoruniversityotherLEBANON
dc.contributor.countryeditoruniversityotherGERMANY
dc.subject.ddclabelRecherche opérationnelleen
dc.relation.ispartofisbn978-3-319-13074-3en
dc.relation.conftitle25th International Symposium, ISAAC 2014en
dc.relation.confdate2014-12
dc.relation.confcityJeonjuen
dc.relation.confcountrySouth Koreaen
dc.relation.forthcomingnonen
dc.identifier.doi10.1007/978-3-319-13075-0_38en
dc.description.ssrncandidatenonen
dc.description.halcandidateouien
dc.description.readershiprechercheen
dc.description.audienceInternationalen
dc.relation.Isversionofjnlpeerreviewedouien
dc.relation.Isversionofjnlpeerreviewedouien
dc.date.updated2017-01-16T10:19:55Z
hal.person.labIds86309*
hal.person.labIds989*
hal.person.labIds215382*
hal.person.labIds87731*
hal.faultCode{"duplicate-entry":{"hal-01505529":{"doi":"1.0"}}}


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record