Editing Set cover problem (section)

==Linear program formulation{{Anchor|LP}}==
The '''set cover problem''' can be formulated as the following [[integer linear program]] (ILP).<ref>{{harvtxt|Vazirani|2001|p=108}}</ref>
{|
| minimize
| <math>\sum_{s \in \mathcal S} x_s</math>
|
| (minimize the number of sets)
|-
| subject to
| <math>\sum_{s\colon e \in s} x_s \geqslant 1 </math>
| for all <math>e\in \mathcal U</math>
| (cover every element of the universe)
|-
|
| <math>x_s \in \{0,1\}</math>
| for all <math>s\in \mathcal S</math>.
| (every set is either in the set cover or not)
|}
For a more compact representation of the covering constraint, one can define an [[incidence matrix]] ''<math>A</math>'', where each row corresponds to an element and each column corresponds to a set, and ''<math>A_{e,s}=1</math>'' if element e is in set s, and ''<math>A_{e,s}=0</math>'' otherwise. Then, the covering constraint can be written as <math>A x \geqslant 1 </math>.

'''Weighted set cover''' is described by a program identical to the one given above, except that the objective function to minimize is <math>\sum_{s \in \mathcal S} w_s x_s</math>, where <math>w_{s}</math> is the weight of set <math>s\in \mathcal{S}</math>.

'''Fractional set cover''' is described by a program identical to the one given above, except that <math>x_s</math> can be non-integer, so the last constraint is replaced by <math>0 \leq x_s\leq 1</math>.

This linear program belongs to the more general class of LPs for [[covering problem]]s, as all the coefficients in the objective function and both sides of the constraints are non-negative. The [[Linear programming relaxation#Approximation and integrality gap|integrality gap]] of the ILP is at most <math>\scriptstyle \log n</math> (where <math>\scriptstyle n</math> is the size of the universe). It has been shown that its [[Linear programming relaxation|relaxation]] indeed gives a factor-<math>\scriptstyle \log n</math> [[approximation algorithm]] for the minimum set cover problem.<ref>{{harvtxt|Vazirani|2001|pp=110–112}}</ref> See [[randomized rounding#setcover]] for a detailed explanation.