8
$\begingroup$

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.

$\endgroup$
9
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ 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 $$ $\endgroup$ – prubin Sep 25 at 1:39
  • $\begingroup$ @prubin Yes, thanks. Corrected just now. $\endgroup$ – RobPratt Sep 25 at 2:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.