LP Relaxation-based Methods

The above formulation can be approximated by first solving the LP relaxation of the problem optimally and then rounding the fractional values to integers. The LP relaxation of the problem is to allow the selection variables $x_j$ to take fractional values between $[0, 1]$. The LP relaxation can be solved in polynomial time and the rounding can be done in $O(n)$. Reference [#!hochbaum!#] introduced a rounding algorithm which is a $p$-approximation algorithm, where $p = max_i\{\sum_j a_{ij}\}$ is the maximum number of sets covering an element. Although this worst case result is not very promising, we are more interested in the average case performance. We refer to the rounding algorithm in [#!hochbaum!#] as the fixed-rounding (FR) algorithm:

Step 0:	Solve the LP relaxation of the problem
	and let $\{x_j^*\}$ be the optimal solution;
Step 1:	Output sets $= \{j\vert x_j^* \geq \frac{1}{p}\}$.

The intermediate solution for the LP relaxation naturally provides a lower bound $= \sum_j x_j^*$ for the set cover problem, since the fractional solution is an optimal solution and the LP relaxation is a super set of the set cover problem. We will use this lower bound to evaluate the quality of the solutions produced by our algorithms.

We have also devised an incremental-rounding (IR) algorithm that imposes more restricted rules while selecting sets based on the value of $x_j^*$. Whenever we select a set, we remove all the elements that satisfy the covering constraint in (5.2) due to the newly selected set. Let $M$ denote the union of all elements covered after each step. For the remaining uncovered elements in a set $S_j$, we compute $p_j = \max_i\{\sum_j a_{ij}\}$ for $i \in S_j \backslash M$. Among all the sets that have selection variables greater than the inverse of $p_j$, we choose the set that has the largest number of nodes that have not been covered.

Step 1:	Solve the LP relaxation of the problem
	and let $\{x_j^*\}$ be the optimal solution;
Step 2:	Select set $S_j$ such that :
2(a)	$S_j$ has the largest number of uncovered element;
2(b)	$x_j^* \geq \frac{1}{p_j}$;
Step 3:	Repeat step 2 until all elements are covered.

The correctness of the algorithm holds: for each uncovered node, at least one set has $x_j^* \geq \frac{1}{\sum_j a_{ij}}$ and $p_j \geq \sum_j a_{ij}$. By selecting all sets whose values satisfy 2(b), we are guaranteed to cover all the nodes. Further more, since $p_j$ is non-increasing in each repetition and $p_j \leq p$, the set selection criterion is more restrictive than that in the FR algorithm, which in turn reduces the number of sets selected. Although the worst case bound is the same for both algorithms, we observe from our simulations that the IR algorithm typically performs much better than the FR algorithm.

An alternative to rule 2(a) is to select the set with the greatest $x_j^*$ value, since the larger the value of the selection variable, the more ``essential'' the set may be. For example, if a node is covered by a single set, then the selection variable of this set must be 1 and the set must be selected. However, most of our simulations show that rule 2(a) generally performs better than this alternative rule. One plausible explanation is that rule 2(a) is more objective in attempting to include as many uncovered nodes as possible, while the alternative rule first selects those more ``essential'' sets, which may not contain many nodes.

It is easy to see that both of the algorithms can still have redundant sets in the final solution. To prune these unnecessary extra sets, we use a simple pruning algorithm as the final step to complete the set selection:

Step 1:	Sort all selected sets in increasing order of set size;
Step 2:	Starting from the smallest set, check if it can be removed without leaving any of its nodes uncovered.
Step 3:	Repeat Step 2 until all sets are checked.