# Set Cover:Greedy vs LP

Hi

Both, the greedy and the LP approach for Set Cover give a O(log n) approximation. Is there some inherent difference on the two approximation approaches?

thanks

-

Both greedy and LP are asymptotically optimal approximations. According to a well known result by Ran and Shmuel, getting a better than c log(n) approximation of set cover is equivalent to showing that P = NP. Here is a reference:

Ran, Shmuel (1997), "A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP", STOC '97

In practical terms, they end up doing effectively the same thing, just that linear programming gives a slightly more general perspective on the problem. This is similar to the idea of thinking of network flow as either a special kind of combinatorial graph optimization problem; or thinking of it more generally as another instance of linear programming. The linear programming perspective is often useful for proving some things and connecting results together (for example via duality), while the greedy method suggests a more practical route to implementation and illuminates some of the specific details about the set cover problem.

-
1. You can view the standard greedy set cover algorithm as a derandomization (using the method of conditional probabilities) of the following randomized rounding of the LP solution $x$: repeatedly sample sets from the distribution defined by $x/\|x\|_1$ until the sets form a cover. For details, see here or here.