Editing Set cover problem (section)

== Variants ==
In the '''weighted set cover''' problem, each set is assigned a positive weight (representing its cost), and the goal is to find a set cover with a smallest weight. The usual (unweighted) set cover corresponds to all sets having a weight of 1.

In the '''fractional set cover''' problem, it is allowed to select fractions of sets, rather than entire sets. A fractional set cover is an assignment of a fraction (a number in [0,1]) to each set in <math>\mathcal{S}</math>, such that for each element ''x'' in the universe, the sum of fractions of sets that contain ''x'' is at least 1. The goal is to find a fractional set cover in which the sum of fractions is as small as possible. Note that a (usual) set cover is equivalent to a fractional set cover in which all fractions are either 0 or 1; therefore, the size of the smallest fractional cover is at most the size of the smallest cover, but may be smaller. For example, consider the universe {{math|1=''U'' = {1, 2, 3<nowiki>}</nowiki> }} and the collection of sets {{math|1=''S'' = { {1, 2}, {2, 3}, {3, 1} }.}}  The smallest set cover has a size of 2, e.g. {{math|1={ {1, 2}, {2, 3} }.}} But there is a fractional set cover of size 1.5, in which a 0.5 fraction of each set is taken. {{Covering-Packing Problem Pairs}}