Show simple item record

Data Reductions and Combinatorial Bounds for Improved Approximation Algorithms

hal.structure.identifier
dc.contributor.authorAbu-Khzam, Faisal N.*
hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorBazgan, Cristina*
hal.structure.identifierLaboratoire d'Informatique de Paris 6 [LIP6]
dc.contributor.authorChopin, Morgan*
hal.structure.identifier
dc.contributor.authorFernau, Henning*
dc.date.accessioned2017-01-10T12:36:39Z
dc.date.available2017-01-10T12:36:39Z
dc.date.issued2016
dc.identifier.issn0022-0000
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/16141
dc.language.isoenen
dc.subjectParameterized complexityen
dc.subjectReduction rulesen
dc.subjectMaximization problemsen
dc.subjectPolynomial-time approximationen
dc.subjectDomination problemsen
dc.subject.ddc003en
dc.subject.classificationjelC.C4.C44en
dc.titleData Reductions and Combinatorial Bounds for Improved Approximation Algorithmsen
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenKernelization algorithms in the context of Parameterized Complexity are often based on a combination of data 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.relation.isversionofjnlnameJournal of Computer and System Sciences
dc.relation.isversionofjnlvol82en
dc.relation.isversionofjnlissue3en
dc.relation.isversionofjnldate2016-05
dc.relation.isversionofjnlpages503-520en
dc.relation.isversionofdoi10.1016/j.jcss.2015.11.010en
dc.identifier.urlsitehttps://arxiv.org/abs/1409.3742v1
dc.contributor.countryeditoruniversityotherLEBANON
dc.contributor.countryeditoruniversityotherGERMANY
dc.relation.isversionofjnlpublisherElsevieren
dc.subject.ddclabelRecherche opérationnelleen
dc.relation.forthcomingnonen
dc.relation.forthcomingprintnonen
dc.description.ssrncandidatenonen
dc.description.halcandidateouien
dc.description.readershiprechercheen
dc.description.audienceInternationalen
dc.relation.Isversionofjnlpeerreviewedouien
dc.relation.Isversionofjnlpeerreviewedouien
dc.date.updated2017-01-10T12:24:57Z
hal.identifierhal-01430909*
hal.version1*
hal.update.actionupdateMetadata*
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record