Show simple item record

hal.structure.identifierInstitute for Computer Science and Control [Budapest] [SZTAKI]
dc.contributor.authorBonnet, Édouard
HAL ID: 171728
ORCID: 0000-0002-1653-5822
*
hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorPaschos, Vangelis*
hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorSikora, Florian
HAL ID: 742949
ORCID: 0000-0003-2670-6258
*
dc.date.accessioned2016-12-07T09:32:58Z
dc.date.available2016-12-07T09:32:58Z
dc.date.issued2016
dc.identifier.issn1290-385X
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/16070
dc.language.isoenen
dc.subjectParameterized complexity
dc.subjectparameterized approximation
dc.subjectmax k-set cover
dc.subject.ddc003en
dc.subject.classificationjelC.C6.C69en
dc.titleParameterized exact and approximation algorithms for maximum k-set cover and related satisfiability problems
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenGiven a family of subsets S over a set of elements X and two integers p and k, max k-set cover consists of finding a subfamily T ⊆ S of cardinality at most k, covering at least p elements of X. This problem is W[2]-hard when parameterized by k, and FPT when parameterized by p. We investigate the parameterized approximability of the problem with respect to parameters k and p. Then, we show that max sat-k, a satisfiability problem generalizing max k-set cover, is also FPT with respect to parameter p.
dc.relation.isversionofjnlnameRAIRO - Theoretical Informatics and Applications
dc.relation.isversionofjnlvol50
dc.relation.isversionofjnlissue3
dc.relation.isversionofjnldate2016
dc.relation.isversionofjnlpages227-240
dc.relation.isversionofdoi10.1051/ita/2016022
dc.identifier.urlsitehttps://arxiv.org/abs/1309.4718v3
dc.subject.ddclabelRecherche opérationnelleen
dc.relation.forthcomingnonen
dc.relation.forthcomingprintnonen
dc.description.ssrncandidatenon
dc.description.halcandidateoui
dc.description.readershiprecherche
dc.description.audienceInternational
dc.relation.Isversionofjnlpeerreviewednon
dc.date.updated2016-12-07T09:33:38Z
hal.identifierhal-01505479*
hal.version1*
hal.update.actionupdateMetadata*
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