
On the Minimum Hitting Set of Bundles Problem
Gourvès, Laurent; Bampis, Evripidis; Angel, Eric (2009), On the Minimum Hitting Set of Bundles Problem, Theoretical Computer Science, 410, 45, p. 4534-4542. http://dx.doi.org/10.1016/j.tcs.2009.08.017
View/ Open
Type
Article accepté pour publication ou publiéDate
2009Journal name
Theoretical Computer ScienceVolume
410Number
45Publisher
Elsevier
Pages
4534-4542
Publication identifier
Metadata
Show full item recordAbstract (EN)
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 E={e1,e2,…,en}E={e1,e2,…,en} of nn elements. Each element eiei (i=1,…,ni=1,…,n) has a positive cost cici. A bundlebb is a subset of EE. We are also given a collection S={S1,S2,…,Sm}S={S1,S2,…,Sm} of mm sets of bundles. More precisely, each set SjSj (j=1,…,mj=1,…,m) is composed of g(j)g(j) distinct bundles View the MathML sourcebj1,bj2,…,bjg(j). A solution to mhsb is a subset E′⊆EE′⊆E such that for every Sj∈SSj∈S at least one bundle is covered, i.e. View the MathML sourcebjl⊆E′ for some l∈{1,2,…,g(j)}l∈{1,2,…,g(j)}. The total cost of the solution, denoted by C(E′)C(E′), is ∑{i∣ei∈E′}ci∑{i∣ei∈E′}ci. The goal is to find a solution with a minimum total cost. We give a deterministic View the MathML sourceN(1−(1−1N)M)-approximation algorithm, where NN is the maximum number of bundles per set and MM is the maximum number of sets in which an element can appear. 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.361.36 when N=2N=2 and N−1−ϵN−1−ϵ when N≥3N≥3. It has to be noticed that the application of our algorithm in the case of the min kk-sat problem matches the best known approximation ratio.Subjects / Keywords
Minimum hitting set; Min k-sat; Approximation algorithmRelated items
Showing items related by title and author.
-
Angel, Eric; Bampis, Evripidis; Gourvès, Laurent (2008) Communication / Conférence
-
Angel, Eric; Bampis, Evripidis; Gourvès, Laurent (2007) Document de travail / Working paper
-
Angel, Eric; Bampis, Evripidis; Gourvès, Laurent (2003) Communication / Conférence
-
Angel, Eric; Bampis, Evripidis; Gourvès, Laurent (2004) Article accepté pour publication ou publié
-
Angel, Eric; Bampis, Evripidis; Gourvès, Laurent; Monnot, Jérôme (2005) Communication / Conférence