Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. 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
    
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). –  FiniteA Dec 13 '11 at 4:58

1 Answer 1

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.

share|improve this answer

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.