dc.contributor.author Angel, Eric dc.contributor.author Bampis, Evripidis dc.contributor.author Gourvès, Laurent dc.date.accessioned 2010-07-06T09:50:04Z dc.date.available 2010-07-06T09:50:04Z dc.date.issued 2008 dc.identifier.uri https://basepub.dauphine.fr/handle/123456789/4554 dc.language.iso en en dc.subject approximation algorithm en dc.subject min k −sat en dc.subject minimum hitting set en dc.subject.ddc 003 en dc.title On the Minimum Hitting Set of Bundles Problem en dc.type Communication / Conférence dc.description.abstracten We 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.citationpages 3-14 en dc.relation.ispartofseriestitle Lecture Notes in Computer Science dc.relation.ispartofseriesnumber 5034 dc.relation.ispartoftitle Algorithmic Aspects in Information and Management, 4th International Conference, AAIM 2008, Shanghai, China, June 23-25, 2008. Proceedings en dc.relation.ispartofeditor Fleischer, Rudolf dc.relation.ispartofeditor Xu, Jinhui dc.relation.ispartofpublname springer en dc.relation.ispartofpublcity Berlin en dc.relation.ispartofdate 2008 dc.relation.ispartofurl http://dx.doi.org/10.1007/978-3-540-68880-8 en dc.description.sponsorshipprivate oui en dc.subject.ddclabel Recherche opérationnelle en dc.relation.ispartofisbn 978-3-540-68865-5 en dc.relation.conftitle 4th International Conference on Algorithmic Aspects in Information and Management (AAIM 2008) en dc.relation.confdate 2008-06 dc.relation.confcity Shanghaï en dc.relation.confcountry Chine en dc.identifier.doi http://dx.doi.org/10.1007/978-3-540-68880-8_3
﻿

## Files in this item

FilesSizeFormatView

There are no files associated with this item.