Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
    
I don't understand what you mean by "picking any non-zero x_S also gives the same approximation factor." and I also don't understand your main question, which is probably related? –  Dave Pritchard Apr 5 '12 at 5:21
add comment

1 Answer

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.