Question

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.

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

Answer 1

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