On the minimum hitting set of bundles problem

作     者：Angel, Eric Bampis, Evripidis Gourves, Laurent 

作者机构：CNRS FRE 3234 F-75775 Paris France Univ Evry IBISC CNRS Evry France Univ Paris 09 LAMSADE F-75775 Paris France 

出 版 物：《THEORETICAL COMPUTER SCIENCE》 (理论计算机科学)

年 卷 期：2009年第410卷第45期

页      面：4534-4542页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：MINIMUM HITTING SET MIN k-SAT Approximation algorithm 

摘      要：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 epsilon = (e(1), e(2), ... , e(n)} of n elements. Each element e(i) (i = 1, ... , n) has a positive cost c(i). A bundle b is a subset of epsilon. We are also given a collection s = {S-1, S-2, ... , S-m} of m sets of bundles. More precisely, each set S-j (j = 1, ... , m) is composed of g(j) distinct bundles b(j)(1), b(j)(2), ... ,b(j)(g(j)). A solution to MHSB is a subset epsilon subset of epsilon such that for every S-j is an element of S at least one bundle is covered, i.e. b(j)(l) subset of epsilon for some l is an element of {1, 2, ... , g(j)}. The total cost of the solution, denoted by C(epsilon ), is Sigma(vertical bar i vertical bar ej is an element of epsilon vertical bar) ci. The goal is to find a solution with a 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 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.36 when N = 2 and N - 1 - epsilon 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. (C) 2009 Elsevier B.V. All rights reserved.