Show simple item record

dc.contributor.authorAlfandari, Laurent
dc.contributor.authorMonnot, Jérôme
dc.date.accessioned2010-04-28T10:04:47Z
dc.date.available2010-04-28T10:04:47Z
dc.date.issued2010
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/4023
dc.language.isoenen
dc.subjectApproximation
dc.subjectNP-hardness
dc.subjectMaximal Coverage
dc.subjectSet Covering
dc.subjectInteger Programmingen
dc.subject.ddc003en
dc.titleApproximation of the Clustered Set Covering Problemen
dc.typeCommunication / Conférence
dc.description.abstractenWe define a NP-hard clustered variant of the Set Covering Problem where subsets are partitioned into K clusters and a fixed cost is paid for selecting at least one subset in a given cluster. This variant can reformulate as a master problem various multicommodity flow problems in transportation planning. We show that the problem is approximable within ratio (1 + ǫ)(e/e− 1)H(q), where q is the maximum number of elements covered by a cluster and H(q) = Pq i=1 1 i .en
dc.relation.isversionofjnlnameElectronic Notes in Discrete Mathematics
dc.relation.isversionofjnlvol36
dc.relation.isversionofjnldate2010-08
dc.relation.isversionofjnlpages479-485
dc.relation.isversionofdoihttp://dx.doi.org/10.1016/j.endm.2010.05.061
dc.description.sponsorshipprivateouien
dc.relation.isversionofjnlpublisherElsevier
dc.subject.ddclabelRecherche opérationnelleen
dc.relation.conftitleISCO International Symposium on Combinatorial Optimizationen
dc.relation.confdate2010-03
dc.relation.confcityHammameten
dc.relation.confcountryTunisieen


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