3
$\begingroup$

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

  • 0
    Some findings about this question. The case of f=2 is called half-integral. Interestingly, one can find simple example that the optimal solution doesnt have to be multiplies of 1/f. But this result still leave unanswered the question whether there is nothing between (0,1/f).2011-12-13

1 Answers 1

0

I have few steps which might be help you find the solution.

1) The polytope bounded by the LP feasible region, will have a vertex only when $|S| \leq |U|$ (For a vertex, number of active equations = |U|). For the case, $f=2$, $|S|$ and $|U| $corresponds to number of edges and number of vertices respectively. For a connected graph $|S| > |U|$, hence the are no non-degenerate vertices.

2) For higher values of $f$ one could possible map this problem to a hypergraph and try to approach in a similar way.