Here is the simple algorithm for approximating set cover problem using rounding:
Algorithm 14.1 (Set cover via LP-rounding)
Find an optimal solution to the LP-relaxation.
Pick all sets $S$ for which $x_S \geq 1/f$ in this solution.
from Vazirani's Approximation Algorithms.
It can be shown that it achieves approximate factor of $f$ to the integral set cover problem, where $f$ is the maximum frequency that an element is covered. In fact, by using complementary slackness condition, it can also be shown that picking any non-zero $x_S$ also gives the same approximation factor. So I wonder is there any non-degenerate optimal solution that makes use of the interval $(0,1/f)$? By non-degenerate, I mean optimal solution that corresponds to the vertex in the polytope bounded by the LP feasible region.
It is possible to show for $f=2$ using vertex cover, but it is not obvious for higher $f$.
The LP for set cover I'm talking about: Given $U$ the universe and $S$ the family of subsets of $U$:
$$\min\sum_{S}c_Sx_S$$
subject to
$$\sum_{e\in S}x_S\ge1, \forall e\in U$$
$$x_S\ge0$$
The $\{0,1\}$ requirement being relaxed to non-negativity of $x_S$.
