Approximate Set Cover Problem by Rounding 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$.
 A: Yes, I believe there are instances of set cover where optimal basic feasible solutions (vertices of the polytope) have coordinates in $(0,1/f)$.  Here is (I think) an example with $f=3$.
Create 13 sets: $A_1,A_2,\ldots,A_6$ and $B_1,B_2,\ldots,B_6$ and $C$.
Populate the $\{A_i\}$ sets with $6\choose 2$ new elements $\{a_j\}$, where each element occurs in a distinct pair of the $A$ sets.  Populate the $\{B_i\}$ sets with $6 \choose 3$ new elements $\{b_j\}$, where each element occurs in a distinct triple of the $B$ sets.  Populate $C$ with $6$ new elements $\{c_j\}$, and, for $i=1..6$, also add each $c_i$ to both $A_i$ and $B_i$.
I claim the unique optimal fractional set cover $X^+$ is as follows.
For each $i$, $X^+(A_i) = 1/2$ and $X^+(B_i) = 1/3$, and $X^+(C)=1/6$.
It is easy to verify that this is a cover of cost $5+1/6$.
To finish we show that there is no other cover of the same or lesser cost.
Let $X$ be any cover of the same or lesser cost.
Let $x_a$ be the average of the $X(A_i)$'s.  Let $x_b$ be the average of the $X(B_i)$'s.
Let $x_c = X(C)$. Then the cost of $X$ is $6x_a + 6x_b + x_c$.
By symmetry and the choice of the elements, $x_a\ge 1/2$, and $x_b\ge 1/3$, and (since $X$ covers each element in $C$) $x_c \ge 1-x_a-x_b$. These facts imply that the cost cannot be less than $5+1/6$, so must equal $5+1/6$, and it must be that $x_a = 1/2$ and $x_b = 1/3$ and $x_c=1/6$.
Suppose for contradiction that $X(A_i) = 1/2-\epsilon$ for some $i$ and some $\epsilon>0$.
Then (just considering the elements $\{a_j\}$), every other $X(A_{i'})$ has to be at least $1/2+\epsilon$, so the average of the $X(A_i)$'s exceeds $1/2$, contradicting $x_a =1/2$.  So, each $X(A_i)$ equals $1/2$.
Likewise, suppose for contradiction that $X(B_i) = 1/3-\epsilon$ for some $i$ and some $\epsilon>0$.  Then (just considering the elements $\{b_j\}$), every other pair $X(B_{i'})$ and $X(B_{i''})$ has to sum to at least $2/3+\epsilon$.  So, the average of the other $X(B_{i'})$'s has to be at least $1/3+\epsilon/2$. Since there are five other $X(B_{i'})$'s, this contradicts $x_b = 1/3$.  So, each $X(B_i)$ equals $1/3$.
Thus, $X$ is the same as $X^+$.
