On the minimum hitting set of bundles problem

International audienceWe 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} of n elements. Each element ei (i = 1, . . . , n) has a non negative cost ci. A bundle b is a subset of E. We are also given a collection S = {S1, S2, . . . , Sm} of m sets of bundles. More precisely, each set Sj (j = 1, . . . ,m) is composed of g(j) distinct bundles b1j, b2j , . . . , bg(j) j . A solution to mhsb is a subset E0 E such that for every Sj 2 S at least one bundle is covered, i.e. bl j E0 for some l 2 {1, 2, * * * , g(j)}. The total cost of the solution, denoted by C(E0), is P{i|ei2E0} ci. The goal is to find a solution with minimum total cost. We give a deterministic N(1−(1− 1 N )M)-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