Editing Set cover problem (section)

== Low-frequency systems ==

If each element occurs in at most {{var|f}} sets, then a solution can be found in polynomial time that approximates the optimum to within a factor of {{var|f}} using [[Linear programming relaxation|LP relaxation]].

If the constraint <math>x_S\in\{0,1\}</math> is replaced by <math>x_S \geq 0</math> for all {{var|S}} in <math>\mathcal{S}</math> in the integer linear program shown [[#Integer linear program formulation|above]], then it becomes a (non-integer) linear program {{var|L}}. The algorithm can be described as follows:
# Find an optimal solution {{var|O}} for the program {{var|L}} using some polynomial-time method of solving linear programs.
# Pick all sets {{var|S}} for which the corresponding variable {{var|x}}<sub>{{var|S}}</sub> has value at least 1/{{var|f}} in the solution {{var|O}}.<ref>{{harvtxt|Vazirani|2001|pp=118–119}}</ref>