Question

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

Answer 1

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.

Answer 2

This is really a comment, not an answer, but for whatever reason I see no comment field.

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.

2. Although greedy algorithms are often faster and easier to implement than solving the LP and rounding it, in practice, solving and rounding the LP might well give you better results, especially for "easy" instances for which many coordinates of the LP turn out to be integral.