Approximate Set Cover Problem by Rounding - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-20T12:06:47Z http://mathoverflow.net/feeds/question/83091 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/83091/approximate-set-cover-problem-by-rounding Approximate Set Cover Problem by Rounding FiniteAutomata 2011-12-10T00:34:35Z 2012-11-05T08:09:29Z <p>Here is the simple algorithm for approximating set cover problem using rounding:</p> <blockquote> <p>Algorithm 14.1 (Set cover via LP-rounding)</p> <ol> <li><p>Find an optimal solution to the LP-relaxation.</p></li> <li><p>Pick all sets $S$ for which $x_S \geq 1/f$ in this solution.</p></li> </ol> </blockquote> <p>from Vazirani's <a href="http://www.cc.gatech.edu/fac/Vijay.Vazirani/book.pdf" rel="nofollow"><em>Approximation Algorithms</em></a>.</p> <p>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.</p> <p>It is possible to show for $f=2$ using vertex cover, but it is not obvious for higher $f$.</p> <p>The LP for set cover I'm talking about: Given $U$ the universe and $S$ the family of subsets of $U$:</p> <p>$$\min\sum_{S}c_Sx_S$$</p> <p>subject to</p> <p>$$\sum_{e\in S}x_S\ge1, \forall e\in U$$</p> <p>$$x_S\ge0$$</p> <p>The ${0,1}$ requirement being relaxed to non-negativity of $x_S$.</p> http://mathoverflow.net/questions/83091/approximate-set-cover-problem-by-rounding/111535#111535 Answer by Neal for Approximate Set Cover Problem by Rounding Neal 2012-11-05T08:09:29Z 2012-11-05T08:09:29Z <p>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$.</p> <p>Create 13 sets: $A_1,A_2,\ldots,A_6$ and $B_1,B_2,\ldots,B_6$ and $C$.</p> <p>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$.</p> <p>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$.</p> <p>To finish we show that there is no other cover of the same or lesser cost.</p> <p>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$.</p> <p>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$.</p> <p>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$.</p> <p>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$.</p> <p>Thus, $X$ is the same as $X^+$.</p>