Specific algorithms to compute the LP-relaxation of the Set-Cover problem

Question

One of the most commonly known combinatorial problems is the set cover problem, which states that given a collection of sets $S = \{s_1, \dots, s_m\}$ and a universe of elements $U = \bigcup_{i=1}^m s_i$ we should select the minimum number of sets from $S$ such that the union of those sets is equal to $U$.

The LP-relaxation of this problem often pops up in OR techniques and it can obviously be solved in polynomial time with an LP-solver using the following formulation: $$ \begin{array}{llll} \min & \sum_{i \in \{1, \dots, m\}} x_i \\ \mbox{s.t.} & \sum_{i \in \{1, \dots, m\} \land j \in s_i} x_i & \geq 1 & \forall j \in U \\ & x_i & \geq 0 & \forall i \in \{1, \dots, m\}\\ \end{array} $$

However, contrary to some other "classical" combinatorial problems that can be solved in polynomial time, I do not know any other algorithm than using an LP-solver. For the knapsack problem, for example, you can sort the items and use a greedy algorithm to obtain the LP-relaxation. For shortest path and network flow there also many well known algorithms that can be implemented in a reasonable about of time. The only result I know for set cover, is that we can use a greedy algorithm to obtain a $\ln |U| + 1$ approximation, but this algorithm does not consider the option to select sets fractionally (which is allowed in the LP-relaxation).

My question is whether there are more specific algorithms than general LP-solvers that give you the optimal solution to the LP-relaxation of the set cover problem. As a bonus, it would be nice if it is easy to implement.

Answer 1

Not sure about solving the LP relaxation, but you can get a closed-form lower bound from LP duality, without calling any solver. Let $y_j$ be the dual variable for constraint $j\in U$. The dual LP is to maximize $\sum_j y_j$ subject to \begin{align} \sum_{j \in s_i} y_j &\le 1 &&\text{for $i\in \{1,\dots,m\}$} \\ y_j &\ge 0 &&\text{for $j\in U$} \end{align} Now $$y_j=\min_{\substack{i\in\{1,\dots,m\}:\\ j \in s_i}} \frac{1}{|s_i|}$$ is dual feasible and hence the dual objective value $$\sum_{j\in U} \min_{\substack{i\in\{1,\dots,m\}:\\ j \in s_i}} \frac{1}{|s_i|}$$ is a valid lower bound.