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

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.

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.
• Rob, I agree with the dual feasible solution and lower bound, but shouldn't the dual constraint be the following? $$\sum_{j\in s_i} y_j \le 1 \quad \forall i$$ – prubin Sep 25 '20 at 1:39