2000 · 62 citations · 21 references
Natural SciencesComputer ScienceMathematicsAlgorithmsCombinatoricsSet TheoryApproximation AlgorithmsCombinatorial OptimizationGraph AlgorithmsGreedy AlgorithmsHeuristic OptimizationMatroid TheoryGreedy HeuristicsHeuristicsLinear Function ApproximationSet CoverSet Cover ApproximationSet Cover ProblemSet Covering Problem
Introduction We start with the set cover( SC ) problem. Given a finite set M and a family N of subsets of M , a subfamily S of N is called a set cover if every element of M appears in some subset in S; in other words, the union of all subsets in S coincides with M . Each set in N is associated with a (U"C2T0"'# e) cost, and the cost of a family is the sum of costs of subsets in it. The set cover problem then asks to find a minimum cost set cover. As a special case when all the costs associated with sets are identical, it is called the unit cost set cover, and it is one of the basic NP-complete optimization problems presented by Karp [17]. he problem is also equivalent to the hitting set problem and the dominating set problem on gra
21
A Greedy Heuristic for the Set-Covering Problem
Vašek Chvátal · Mathematics of Operations Research · 1979 · 2.6K citations