Here is the simple algorithm for approximating set cover problem using rounding:
> Algorithm 14.1 (Set cover via LP-rounding)
>
> 1. Find an optimal solution to the LP-relaxation.
>
> 2. Pick all sets $S$ for which $x_S \geq 1/f$ in this solution.

from Vazirani's [*Approximation Algorithms*][1].

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$.


  [1]: http://www.cc.gatech.edu/fac/Vijay.Vazirani/book.pdf