Show simple item record

On the Minimum Hitting Set of Bundles Problem

dc.contributor.authorAngel, Eric
dc.contributor.authorBampis, Evripidis
dc.contributor.authorGourvès, Laurent
dc.date.accessioned2010-07-06T09:50:04Z
dc.date.available2010-07-06T09:50:04Z
dc.date.issued2008
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/4554
dc.language.isoenen
dc.subjectapproximation algorithmen
dc.subjectmin k −saten
dc.subjectminimum hitting seten
dc.subject.ddc003en
dc.titleOn the Minimum Hitting Set of Bundles Problemen
dc.typeCommunication / Conférence
dc.description.abstractenWe consider a natural generalization of the classical minimum hitting set problem, the minimum hitting set of bundles problem (mhsb) which is defined as follows. We are given a set TeX of n elements. Each element e i (i = 1, ...,n) has a non negative cost c i . A bundle b is a subset of TeX . We are also given a collection TeX of m sets of bundles. More precisely, each set S j (j = 1, ..., m) is composed of g(j) distinct bundles TeX . A solution to mhsb is a subset TeX such that for every TeX at least one bundle is covered, i.e. TeX for some l ∈ {1,2, ⋯ ,g(j)}. The total cost of the solution, denoted by TeX , is TeX . The goal is to find a solution with minimum total cost. We give a deterministic TeX -approximation algorithm, where N is the maximum number of bundles per set and M is the maximum number of sets an element can appear in. This is roughly speaking the best approximation ratio that we can obtain since, by reducing mhsb to the vertex cover problem, it implies that mhsb cannot be approximated within 1.36 when N = 2 and N − 1 − ε when N ≥ 3. It has to be noticed that the application of our algorithm in the case of the min k −sat problem matches the best known approximation ratio.
dc.identifier.citationpages3-14en
dc.relation.ispartofseriestitleLecture Notes in Computer Science
dc.relation.ispartofseriesnumber5034
dc.relation.ispartoftitleAlgorithmic Aspects in Information and Management, 4th International Conference, AAIM 2008, Shanghai, China, June 23-25, 2008. Proceedingsen
dc.relation.ispartofeditorFleischer, Rudolf
dc.relation.ispartofeditorXu, Jinhui
dc.relation.ispartofpublnamespringeren
dc.relation.ispartofpublcityBerlinen
dc.relation.ispartofdate2008
dc.relation.ispartofurlhttp://dx.doi.org/10.1007/978-3-540-68880-8en
dc.description.sponsorshipprivateouien
dc.subject.ddclabelRecherche opérationnelleen
dc.relation.ispartofisbn978-3-540-68865-5en
dc.relation.conftitle4th International Conference on Algorithmic Aspects in Information and Management (AAIM 2008)en
dc.relation.confdate2008-06
dc.relation.confcityShanghaïen
dc.relation.confcountryChineen
dc.identifier.doihttp://dx.doi.org/10.1007/978-3-540-68880-8_3


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